On the public citation graph
On the power of parity polynomial time
0 signed · 126 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-16486-3_85openalex-snapshot
The complexity of sparse sets in P
inferredcites →https://doi.org/10.1007/3-540-16486-3_92openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bfb0017131openalex-snapshot
Structure of complexity classes: Separations, collapses, and completeness
inferredcites →https://doi.org/10.1007/bfb0028987openalex-snapshot
On the power of parity polynomial time
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0020-0190(76)90097-1openalex-snapshot
Relative complexity of checking and evaluating
inferredcites →https://doi.org/10.1016/0020-0190(87)90036-6openalex-snapshot
Random oracles separate PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(82)90002-2openalex-snapshot
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
inferredcites →https://doi.org/10.1016/0022-0000(89)90033-0openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(85)90140-9openalex-snapshot
Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
inferredcites →https://doi.org/10.1016/0304-3975(86)90165-9openalex-snapshot
On the construction of parallel computers from various bases of boolean functions
inferredcites →https://doi.org/10.1016/0304-3975(88)90022-9openalex-snapshot
Complexity classes without machines: On complete languages for UP
inferredcites →https://doi.org/10.1016/0304-3975(91)90160-4openalex-snapshot
Bounded queries to SAT and the Boolean hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferredcites →https://doi.org/10.1016/0890-5401(89)90063-1openalex-snapshot
Enumerative counting is hard
inferredcites →https://doi.org/10.1016/s0019-9958(82)90439-9openalex-snapshot
On the unique satisfiability problem
inferredcites →https://doi.org/10.1051/ita/1987210404191openalex-snapshot
The difference and truth-table hierarchies for NP
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/psct.1987.10319254openalex-snapshot
Self-Reducible, P-Selective, Near-Testable, and P-Cheatable Sets: The Effect of Internal Structure on the Complexity of a Set
inferredcites →https://doi.org/10.1109/sct.1989.41826openalex-snapshot
Turning machines with few accepting computations and low sets for PP
inferredcites →https://doi.org/10.1109/sct.1989.41828openalex-snapshot
On the power of probabilistic polynomial time: P/sup NP(log)/ contained in PP
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0211026openalex-snapshot
On the Accepting Density Hierarchy in NP
inferredcites →https://doi.org/10.1137/0212027openalex-snapshot
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
inferredcites →https://doi.org/10.1137/0212038openalex-snapshot
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
inferredcites →https://doi.org/10.1137/0217018openalex-snapshot
Complexity Measures for Public-Key Cryptosystems
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0217078openalex-snapshot
The Boolean Hierarchy I: Structural Properties
inferredcites →https://doi.org/10.1137/0218007openalex-snapshot
The Boolean Hierarchy II: Applications
inferredcites →https://doi.org/10.1145/12130.12160openalex-snapshot
A note on one-way functions and polynomial-time isomorphisms
inferredcites →https://doi.org/10.1145/5925.5938openalex-snapshot
Relativizing complexity classes with sparse oracles
inferredcites →https://doi.org/10.7916/d83x8frjopenalex-snapshot
On the Power of Probabilistic Polynomial Time: PNP[log] ⊆ PP
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1996.0080openalex-snapshot
Gap-Definability as a Closure Property
inferred← citeshttps://doi.org/10.1006/inco.1999.2810openalex-snapshot
Tally NP Sets and Easy Census Functions
inferred← citeshttps://doi.org/10.1006/jcss.1996.0059openalex-snapshot
On Closure Properties of #P in the Context of PF∘#P
inferred← citeshttps://doi.org/10.1006/jcss.1997.1516openalex-snapshot
Universally Serializable Computation
inferred← citeshttps://doi.org/10.1006/jcss.1999.1646openalex-snapshot
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
inferred← citeshttps://doi.org/10.1007/3-540-48321-7_9openalex-snapshot
Restrictive acceptance suffices for equivalence problems
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_71openalex-snapshot
Algorithms from complexity theory: Polynomial-time operations for complex sets
inferred← citeshttps://doi.org/10.1007/3-540-55719-9_72openalex-snapshot
Reductions to sets of low information content
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_48openalex-snapshot
Gap-definability as a closure property
inferred← citeshttps://doi.org/10.1007/978-0-387-35608-2_19openalex-snapshot
Lower Bounds and the Hardness of Counting Properties
inferred← citeshttps://doi.org/10.1007/978-3-540-24597-1_32openalex-snapshot
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties
inferred← citeshttps://doi.org/10.1007/bf01263424openalex-snapshot
Representing Boolean functions as polynomials modulo composite numbers
inferred← citeshttps://doi.org/10.1007/bf01368782openalex-snapshot
Simultaneous strong separations of probabilistic and unambiguous complexity classes
inferred← citeshttps://doi.org/10.1007/bf01578841openalex-snapshot
Generalized theorems on relationships among reducibility notions to certain complexity classes
inferred← citeshttps://doi.org/10.1007/bf02679447openalex-snapshot
Helping by Unambiguous Computation and Probabilistic Computation
inferred← citeshttps://doi.org/10.1007/bfb0023873openalex-snapshot
Banishing robust Turing completeness
inferred← citeshttps://doi.org/10.1007/bfb0028561openalex-snapshot
On the structure of valiant's complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0028583openalex-snapshot
Optimal proof systems for propositional logic and complete sets
inferred← citeshttps://doi.org/10.1007/bfb0029617openalex-snapshot
On checking versus evaluation of multiple queries
inferred← citeshttps://doi.org/10.1007/bfb0029633openalex-snapshot
Separating ⊕L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time
inferred← citeshttps://doi.org/10.1007/bfb0035749openalex-snapshot
Limitations of the upward separation technique (preliminary version)
inferred← citeshttps://doi.org/10.1007/bfb0055791openalex-snapshot
A second step towards circuit complexity-theoretic analogs of Rice's theorem
inferred← citeshttps://doi.org/10.1007/bfb0055798openalex-snapshot
Tally NP sets and easy census functions
inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
inferred← citeshttps://doi.org/10.1007/s00037-008-0248-yopenalex-snapshot
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers
inferred← citeshttps://doi.org/10.1007/s00037-012-0047-3openalex-snapshot
On the power of unambiguity in log-space
inferred← citeshttps://doi.org/10.1007/s00224-018-9893-yopenalex-snapshot
Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90140-dopenalex-snapshot
Probabilistic polynomial time is closed under parity reductions
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90002-dopenalex-snapshot
On the power of enumerative counting
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00232-nopenalex-snapshot
On helping by parity-like languages
inferred← citeshttps://doi.org/10.1016/0020-0190(94)90123-6openalex-snapshot
Upward separation for FewP and related classes
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00109-popenalex-snapshot
Modulo classes and logarithmic advice
inferred← citeshttps://doi.org/10.1016/0022-0000(93)90006-iopenalex-snapshot
A complexity theory for feasible closure properties
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90282-7openalex-snapshot
Kolmogorov characterizations of complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90388-iopenalex-snapshot
On sets polynomially enumerable by iteration
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90125-yopenalex-snapshot
A uniform approach to define complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90020-topenalex-snapshot
On sparse hard sets for counting classes
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferred← citeshttps://doi.org/10.1016/j.ic.2004.10.009openalex-snapshot
Quantum and classical complexity classes: Separations, collapses, and closure properties
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105213openalex-snapshot
Weighted automata and logics meet computational complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.03.004openalex-snapshot
Lower bounds and the hardness of counting properties
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.01.005openalex-snapshot
NL-printable sets and nondeterministic Kolmogorov complexity
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80009-1openalex-snapshot
A taxonomy of complexity classes of functions
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80024-8openalex-snapshot
Gap-definable counting classes
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00005-4openalex-snapshot
Unambiguous computations and locally definable acceptance types
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00344-2openalex-snapshot
A second step towards complexity-theoretic analogs of Rice's Theorem
inferred← citeshttps://doi.org/10.1016/s0890-5401(03)00058-0openalex-snapshot
Optimal proof systems imply complete sets for promise classes
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)80838-7openalex-snapshot
NL-printable sets and Nondeterministic Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1051/ita/1992260605071openalex-snapshot
Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
inferred← citeshttps://doi.org/10.1070/im1994v042n02abeh001537openalex-snapshot
RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
inferred← citeshttps://doi.org/10.1070/im1994v042n03abeh001545openalex-snapshot
ON THE POSSIBILITY OF PERFORMING ANY MULTI-PROVER INTERACTIVE PROOF IN CONSTANTLY MANY ROUNDS
inferred← citeshttps://doi.org/10.1109/ccc.2007.34openalex-snapshot
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers
inferred← citeshttps://doi.org/10.1109/sct.1991.160238openalex-snapshot
Counting classes are at least as hard as the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1109/sct.1991.160240openalex-snapshot
A complexity theory for feasible closure properties
inferred← citeshttps://doi.org/10.1109/sct.1991.160248openalex-snapshot
Complexity classes and sparse oracles
inferred← citeshttps://doi.org/10.1109/sct.1993.336532openalex-snapshot
On closure properties of Hash P in the context of PF (omicron) Hash P
inferred← citeshttps://doi.org/10.1109/sct.1994.315823openalex-snapshot
Polynomial-time membership comparable sets
inferred← citeshttps://doi.org/10.1112/s146115700000022xopenalex-snapshot
Restrictive Acceptance Suffices for Equivalence Problems
inferred← citeshttps://doi.org/10.1137/s0097539705447013openalex-snapshot
The Complexity of Computing the Size of an Interval
inferred← citeshttps://doi.org/10.1137/s0097539793250330openalex-snapshot
Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
inferred← citeshttps://doi.org/10.1137/s0097539793258131openalex-snapshot
Polynomial-Time Membership Comparable Sets
inferred← citeshttps://doi.org/10.1142/s012905419300016xopenalex-snapshot
BANISHING ROBUST TURING COMPLETENESS
inferred← citeshttps://doi.org/10.1142/s0218196711006066openalex-snapshot
THE THOMPSON–HIGMAN MONOIDS M k,i : THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY
inferred← citeshttps://doi.org/10.1145/129712.129756openalex-snapshot
Representing Boolean functions as polynomials modulo composite numbers
inferred← citeshttps://doi.org/10.1145/167088.167213openalex-snapshot
Randomness-optimal unique element isolation, with applications to perfect matching and related problems
inferred← citeshttps://doi.org/10.1145/3652851openalex-snapshot
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
inferred← citeshttps://doi.org/10.48550/arxiv.0904.2479openalex-snapshot
The Thompson-Higman monoids M_{k,i}: the J-order, the D-relation, and their complexity
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0502058openalex-snapshot
The Complexity of Computing the Size of an Interval
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9809002openalex-snapshot
Tally NP Sets and Easy Census Functions
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9907041openalex-snapshot
Restrictive Acceptance Suffices for Equivalence Problems
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.