On the public citation graph

New Lowness Results for ZPPNP and Other Complexity Classes

https://doi.org/10.1006/jcss.2002.1835
0 signed · 36 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/jcss.1996.0032openalex-snapshot
Oracles and Queries That Are Sufficient for Exact Learning
inferredcites →https://doi.org/10.1007/978-1-4613-3394-4openalex-snapshot
Advances in Algorithms, Languages, and Complexity
inferredcites →https://doi.org/10.1007/978-1-4613-3394-4_6openalex-snapshot
High Sets for NP
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/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
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(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferredcites →https://doi.org/10.1016/0022-0000(90)90025-gopenalex-snapshot
Self-reducibility
inferredcites →https://doi.org/10.1016/0304-3975(93)90256-sopenalex-snapshot
Circuit size relative to pseudorandom oracles
inferredcites →https://doi.org/10.1016/0890-5401(89)90022-9openalex-snapshot
Relativized Arthur-Merlin versus Merlin-Arthur games
inferredcites →https://doi.org/10.1016/s0022-0000(05)80009-1openalex-snapshot
A taxonomy of complexity classes of functions
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1016/s0304-3975(99)00164-4openalex-snapshot
On pseudorandomness and resource-bounded measure
inferredcites →https://doi.org/10.1109/ccc.1996.507683openalex-snapshot
Inverting onto functions
inferredcites →https://doi.org/10.1109/ccc.1998.694585openalex-snapshot
Nonrelativizing separations
inferredcites →https://doi.org/10.1137/0213030openalex-snapshot
Quantitative Relativizations of Complexity Classes
inferredcites →https://doi.org/10.1137/0405008openalex-snapshot
Bounded Round Interactive Proofs in Finite Groups
inferredcites →https://doi.org/10.1137/s0097539795296206openalex-snapshot
New Collapse Consequences of NP Having Small Circuits
inferredcites →https://doi.org/10.1142/s012905419500010xopenalex-snapshot
ON HELPING AND INTERACTIVE PROOF SYSTEMS
inferredcites →https://doi.org/10.1145/116825.116852openalex-snapshot
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
inferredcites →https://doi.org/10.1145/200836.200880openalex-snapshot
Designing programs that check their work
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes

What points at this work

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

inferred← citeshttps://doi.org/10.1007/11537311_37openalex-snapshot
Relations Between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_6openalex-snapshot
Randomized Algorithms and Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot
Other Public-Key Cryptosystems and Protocols
inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
inferred← citeshttps://doi.org/10.1007/s00224-007-9071-0openalex-snapshot
Relations between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1016/j.dam.2006.04.038openalex-snapshot
Complexity results in graph reconstruction
inferred← citeshttps://doi.org/10.1016/j.ipl.2003.09.011openalex-snapshot
AMexp⊈(NP∩coNP)/poly
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.07.015openalex-snapshot
S2p⊆ZPPNP
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.004openalex-snapshot
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
inferred← citeshttps://doi.org/10.1145/3717823.3718143openalex-snapshot
Extractors for Samplable Distributions with Low Min-Entropy
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.