On the public citation graph

Observations on measure and lowness for Δ 2 P

https://doi.org/10.1007/bf02679469
0 signed · 52 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1996.0017openalex-snapshot
Completeness and Weak Completeness under Polynomial-Size Circuits
inferredcites →https://doi.org/10.1007/3-540-60084-1_74openalex-snapshot
New collapse consequences of NP having small circuits
inferredcites →https://doi.org/10.1007/978-1-4612-0333-9openalex-snapshot
The Graph Isomorphism Problem
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/978-3-662-03088-2_3openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1007/bf02088291openalex-snapshot
Generalized lowness and highness and probabilistic complexity classes
inferredcites →https://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(83)90027-2openalex-snapshot
A low and a high hierarchy within NP
inferredcites →https://doi.org/10.1016/0022-0000(85)90040-6openalex-snapshot
Relativized circuit complexity
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(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferredcites →https://doi.org/10.1016/0022-0000(92)90020-jopenalex-snapshot
Almost everywhere high nonuniform complexity
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(91)90320-2openalex-snapshot
An upward measure separation theorem
inferredcites →https://doi.org/10.1016/0304-3975(93)90256-sopenalex-snapshot
Circuit size relative to pseudorandom oracles
inferredcites →https://doi.org/10.1016/0304-3975(94)00023-copenalex-snapshot
Almost every set in exponential time is P-bi-immune
inferredcites →https://doi.org/10.1016/0304-3975(95)00189-1openalex-snapshot
Cook versus Karp-Levin: Separating completeness notions if NP is not small
inferredcites →https://doi.org/10.1016/s0019-9958(86)80044-4openalex-snapshot
A decisive characterization of BPP
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1057/jors.1995.211openalex-snapshot
Introduction to the Theory of Complexity
inferredcites →https://doi.org/10.1109/sct.1993.336530openalex-snapshot
The quantitative structure of exponential time
inferredcites →https://doi.org/10.1109/sct.1995.514863openalex-snapshot
On the structure of low sets [complexity classes]
inferredcites →https://doi.org/10.1109/sfcs.1994.365713openalex-snapshot
Measure on small complexity classes, with applications for BPP
inferredcites →https://doi.org/10.1137/0214003openalex-snapshot
On Circuit-Size Complexity and the Low Hierarchy in NP
inferredcites →https://doi.org/10.1137/0222065openalex-snapshot
A Pseudorandom Oracle Characterization of ${\text{BPP}}$
inferredcites →https://doi.org/10.1137/s0097539792228289openalex-snapshot
The Complexity of Decision Versus Search
inferredcites →https://doi.org/10.1137/s0097539792237498openalex-snapshot
Measure, Stochasticity, and the Density of Hard Languages
inferredcites →https://doi.org/10.1137/s0097539792238133openalex-snapshot
The Complexity and Distribution of Hard Problems
inferredcites →https://doi.org/10.1137/s0097539793249700openalex-snapshot
Weakly Hard Problems
inferredcites →https://doi.org/10.1137/s0097539795296206openalex-snapshot
New Collapse Consequences of NP Having Small Circuits
inferredcites →https://doi.org/10.1145/77600.77623openalex-snapshot
Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
inferredcites →https://doi.org/10.1145/800061.808762openalex-snapshot
A complexity theoretic approach to randomness
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
inferredcites →https://doi.org/10.2307/2584070openalex-snapshot
Introduction to the Theory of Complexity.
inferredcites →https://doi.org/10.31274/rtd-180813-11836openalex-snapshot
The complexity and distribution of computationally useful problems

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcss.1999.1647openalex-snapshot
Two Queries
inferred← citeshttps://doi.org/10.1006/jcss.1999.1650openalex-snapshot
Hard Sets Are Hard to Find
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_176openalex-snapshot
Results on resource-bounded measure
inferred← citeshttps://doi.org/10.1007/bfb0023487openalex-snapshot
Equivalence of measures of complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0058034openalex-snapshot
On resource-bounded measure and pseudorandomness
inferred← citeshttps://doi.org/10.1016/j.ic.2009.02.002openalex-snapshot
A zero-one law for RP and derandomization of AM if NP is not small
inferred← citeshttps://doi.org/10.1016/j.jcss.2005.10.002openalex-snapshot
Dimension, entropy rates, and compression
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.01.037openalex-snapshot
A note on measuring in P
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.02.029openalex-snapshot
The size of SPP
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00164-4openalex-snapshot
On pseudorandomness and resource-bounded measure
inferred← citeshttps://doi.org/10.1109/ccc.1998.694602openalex-snapshot
Hard sets are hard to find
inferred← citeshttps://doi.org/10.1109/ccc.1998.694603openalex-snapshot
On the resource bounded measure of P/poly
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214409openalex-snapshot
A zero one law for RP
inferred← citeshttps://doi.org/10.1109/ccc.2007.7openalex-snapshot
Bounded Queries and the NP Machine Hypothesis
inferred← citeshttps://doi.org/10.1109/sfcs.1997.646149openalex-snapshot
Constant depth circuits and the Lutz hypothesis
inferred← citeshttps://doi.org/10.1145/2601336openalex-snapshot
Hard Instances of Algorithms and Proof Systems
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.