On the public citation graph
On closure properties of bounded two-sided error complexity classes
0 signed · 40 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/978-1-4614-8806-4_7openalex-snapshot
Information and Computation
inferredcites →https://doi.org/10.1007/bf02088291openalex-snapshot
Generalized lowness and highness and probabilistic complexity classes
inferredcites →https://doi.org/10.1007/bfb0020802openalex-snapshot
Randomized polynomials, threshold circuits, and the polynomial hierarchy
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0076220openalex-snapshot
Probabilistic machines, oracles, and quantifiers
inferredcites →https://doi.org/10.1016/0020-0190(82)90139-9openalex-snapshot
Some observations on the probabilistic algorithms and NP-hard problems
inferredcites →https://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
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(81)90021-0openalex-snapshot
A note on structure and looking back applied to the relative complexity of computable functions
inferredcites →https://doi.org/10.1016/0022-0000(88)90010-4openalex-snapshot
Graph isomorphism is in the low hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(88)90037-2openalex-snapshot
Probabilistic quantifiers and games
inferredcites →https://doi.org/10.1016/0022-0000(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
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(82)90039-1openalex-snapshot
Reductions on NP and P-selective sets
inferredcites →https://doi.org/10.1016/0304-3975(82)90085-8openalex-snapshot
Strong nondeterministic polynomial-time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/s0019-9958(82)80019-3openalex-snapshot
Robustness of probabilistic computational complexity classes under definitional perturbations
inferredcites →https://doi.org/10.1016/s0019-9958(86)80044-4openalex-snapshot
A decisive characterization of BPP
inferredcites →https://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
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/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1142/9789812794499_0035openalex-snapshot
COUNTING HIERARCHIES: POLYNOMIAL TIME AND CONSTANT DEPTH CIRCUITS
inferredcites →https://doi.org/10.1145/12130.12133openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/800105.803405openalex-snapshot
Reducibility, randomness, and intractibility (Abstract)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_5openalex-snapshot
Computational Politics: Electoral Systems
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_124openalex-snapshot
Separations by random oracles and “Almost” classes for generalized reducibilities
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_143openalex-snapshot
On type-2 probabilistic quantifiers
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_14openalex-snapshot
Measure One Results in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/bf01184814openalex-snapshot
Strong Self-Reducibility Precludes Strong Immunity
inferred← citeshttps://doi.org/10.1051/ita:1999100openalex-snapshot
Immunity and Simplicity for Exact Counting and Other Counting Classes
inferred← citeshttps://doi.org/10.1109/ccc.1996.507666openalex-snapshot
Collapsing oracle-tape hierarchies
inferred← citeshttps://doi.org/10.1137/s0097539701385958openalex-snapshot
Lattice Embeddings for Abstract Bounded Reducibilities
inferred← citeshttps://doi.org/10.1145/297096.297106openalex-snapshot
Power balance and apportionment algorithms for the United States Congress
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9809001openalex-snapshot
Immunity and Simplicity for Exact Counting and Other Counting Classes
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.