On the public citation graph
Relativized Separations of Worst-Case and Average-Case Complexities for NP
0 signed · 53 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.1002/rsa.3240070103openalex-snapshot
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot
Hiding instances in multioracle queries
inferredcites →https://doi.org/10.1007/978-3-540-24638-1_1openalex-snapshot
Notions of Reducibility between Cryptographic Primitives
inferredcites →https://doi.org/10.1007/978-3-642-14623-7_35openalex-snapshot
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
inferredcites →https://doi.org/10.1007/978-3-642-15369-3_56openalex-snapshot
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
inferredcites →https://doi.org/10.1007/bf01200117openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/s00037-007-0235-8openalex-snapshot
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances
inferredcites →https://doi.org/10.1016/0022-0000(89)90018-4openalex-snapshot
On hiding information from an oracle
inferredcites →https://doi.org/10.1093/oso/9780198536901.003.0012openalex-snapshot
An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic
inferredcites →https://doi.org/10.1109/ccc.2005.11openalex-snapshot
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances
inferredcites →https://doi.org/10.1109/fscs.1990.89604openalex-snapshot
No better ways to generate hard NP instances than picking uniformly at random
inferredcites →https://doi.org/10.1109/sct.1995.514853openalex-snapshot
A personal view of average-case complexity
inferredcites →https://doi.org/10.1109/sfcs.1987.49openalex-snapshot
Random self-reducibility and zero knowledge interactive proofs of possession of information
inferredcites →https://doi.org/10.1109/sfcs.2000.892119openalex-snapshot
Lower bounds on the efficiency of generic cryptographic constructions
inferredcites →https://doi.org/10.1109/sfcs.2003.1238205openalex-snapshot
On Worst‐Case to Average‐Case Reductions for NP Problems
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0222061openalex-snapshot
Random-Self-Reducibility of Complete Sets
inferredcites →https://doi.org/10.1137/0222069openalex-snapshot
On the Existence of Pseudorandom Generators
inferredcites →https://doi.org/10.1142/9789812794499_0019openalex-snapshot
THE CHALLENGER-SOLVER GAME: VARIATIONS ON THE THEME OF P = NP
inferredcites →https://doi.org/10.1145/100216.100226openalex-snapshot
Coherent functions and program checkers
inferredcites →https://doi.org/10.1145/1132516.1132614openalex-snapshot
On basing one-way functions on NP-hardness
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot
P = BPP if E requires exponential circuits
inferredcites →https://doi.org/10.1287/moor.2.3.209openalex-snapshot
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-36030-6_16openalex-snapshot
The Function-Inversion Problem: Barriers and Opportunities
inferred← citeshttps://doi.org/10.1007/978-3-030-56784-2_6openalex-snapshot
Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
inferred← citeshttps://doi.org/10.1007/978-3-031-68385-5_12openalex-snapshot
Tight Characterizations for Preprocessing Against Cryptographic Salting
inferred← citeshttps://doi.org/10.1007/978-3-031-68388-6_16openalex-snapshot
Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions
inferred← citeshttps://doi.org/10.1007/978-3-031-91098-2_13openalex-snapshot
A New Approach to Generic Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-032-01855-7_20openalex-snapshot
Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-08783-2_18openalex-snapshot
A New View on Worst-Case to Average-Case Reductions for NP Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-56614-6_16openalex-snapshot
Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_56openalex-snapshot
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
inferred← citeshttps://doi.org/10.1007/s00037-024-00260-5openalex-snapshot
On the Structure of Learnability beyond P/poly
inferred← citeshttps://doi.org/10.1109/focs.2018.00032openalex-snapshot
Non-Black-Box Worst-Case to Average-Case Reductions within NP
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00068openalex-snapshot
Tight Quantum Time-Space Tradeoffs for Function Inversion
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00078openalex-snapshot
On Worst-Case Learning in Relativized Heuristica
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00095openalex-snapshot
NP-Hardness of Learning Programs and Partial MCSP
inferred← citeshttps://doi.org/10.1137/1.9781611976465.143openalex-snapshot
Concentration bounds for almost k -wise independence with applications to non-uniform security
inferred← citeshttps://doi.org/10.1145/2355580.2355583openalex-snapshot
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
inferred← citeshttps://doi.org/10.1145/2421119.2421135openalex-snapshot
SIGACT News Complexity Theory Column 76
inferred← citeshttps://doi.org/10.1145/3406325.3451065openalex-snapshot
Average-case hardness of NP from exponential worst-case hardness assumptions
inferred← citeshttps://doi.org/10.1145/3519935.3520041openalex-snapshot
Worst-case to average-case reductions via additive combinatorics
inferred← citeshttps://doi.org/10.1145/3564246.3585130openalex-snapshot
Capturing One-Way Functions via NP-Hardness of Meta-Complexity
inferred← citeshttps://doi.org/10.1145/3798129.3800755openalex-snapshot
A Sharp Characterization of Pessiland
inferred← citeshttps://doi.org/10.26083/tuprints-00003414openalex-snapshot
On the Foundations of Key Exchange
inferred← citeshttps://doi.org/10.4230/lipics.approx/random.2020.15openalex-snapshot
On Nonadaptive Security Reductions of Hitting Set Generators
inferred← citeshttps://doi.org/10.48550/arxiv.2006.05650openalex-snapshot
Tight Quantum Time-Space Tradeoffs for Function Inversion
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.