On the public citation graph

Average-case intractability vs. worst-case intractability

0 signed · 69 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.1995.1014openalex-snapshot

On the NP-Isomorphism Problem with Respect to Random Instances

inferredcites →https://doi.org/10.1006/jcss.1995.1036openalex-snapshot

The Power of the Middle Bit of a #P Function

inferredcites →https://doi.org/10.1006/jcss.1995.1037openalex-snapshot

Bounding the Complexity of Advice Functions

inferredcites →https://doi.org/10.1006/jcss.1996.0024openalex-snapshot

Structural Average Case Complexity

inferredcites →https://doi.org/10.1006/jcss.1996.0032openalex-snapshot

Oracles and Queries That Are Sufficient for Exact Learning

inferredcites →https://doi.org/10.1006/jcss.2002.1835openalex-snapshot

New Lowness Results for ZPPNP and Other Complexity Classes

inferredcites →https://doi.org/10.1007/3-540-16079-5openalex-snapshot

Complexity and Structure

inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot

Hiding instances in multioracle queries

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/3-540-60922-9_28openalex-snapshot

Fine separation of average time complexity classes

inferredcites →https://doi.org/10.1007/978-1-4612-1872-2_10openalex-snapshot

The Quantitative Structure of Exponential Time

inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot

Structural Complexity I

inferredcites →https://doi.org/10.1007/bf01200055openalex-snapshot

An editorial

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/bf01201812openalex-snapshot

On the power of generalized Mod-classes

inferredcites →https://doi.org/10.1007/bf01201814openalex-snapshot

Upper Bounds for the Complexity of Sparse and Tally Descriptions

inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

inferredcites →https://doi.org/10.1007/bf02090768openalex-snapshot

On the power of parity polynomial time

inferredcites →https://doi.org/10.1007/bfb0030859openalex-snapshot

Sets computable in polynomial time on average

inferredcites →https://doi.org/10.1007/bfb0055799openalex-snapshot

Average-case intractability vs. worst-case intractability

inferredcites →https://doi.org/10.1007/bfb0058034openalex-snapshot

On resource-bounded measure and pseudorandomness

inferredcites →https://doi.org/10.1007/s002240000060openalex-snapshot

Observations on Measure and Lowness for Δ P_2

inferredcites →https://doi.org/10.1007/s002240000134openalex-snapshot

Robust Reductions

inferredcites →https://doi.org/10.1016/0020-0190(83)90024-8openalex-snapshot

On sparse sets in NP–P

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(84)90013-9openalex-snapshot

Backtrack: An O(1) expected time algorithm for the graph coloring problem

inferredcites →https://doi.org/10.1016/0020-0190(92)90138-lopenalex-snapshot

Average case complexity under the universal distribution equals worst-case complexity

inferredcites →https://doi.org/10.1016/0020-0190(92)90195-2openalex-snapshot

Highly resilient correctors for polynomials

inferredcites →https://doi.org/10.1016/0020-0190(95)00108-oopenalex-snapshot

Some properties of sets tractable under every polynomial-time computable distribution

inferredcites →https://doi.org/10.1016/0022-0000(89)90018-4openalex-snapshot

On hiding information from an oracle

inferredcites →https://doi.org/10.1016/0022-0000(91)90007-ropenalex-snapshot

Average case completeness

inferredcites →https://doi.org/10.1016/0022-0000(92)90019-fopenalex-snapshot

On the theory of average case complexity

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(84)90111-7openalex-snapshot

Computation times of NP sets of different densities

inferredcites →https://doi.org/10.1016/0304-3975(90)90081-ropenalex-snapshot

Relations among mod-classes

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/0304-3975(92)90353-hopenalex-snapshot

Logarithmic advice classes

inferredcites →https://doi.org/10.1016/0304-3975(94)00016-6openalex-snapshot

Locating P/poly optimally in the extended low hierarchy

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(74)90473-2openalex-snapshot

Tally languages and complexity classes

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/s0304-3975(99)00164-4openalex-snapshot

On pseudorandomness and resource-bounded measure

inferredcites →https://doi.org/10.1090/dimacs/002/13openalex-snapshot

New directions in testing

inferredcites →https://doi.org/10.1109/ccc.1996.507681openalex-snapshot

Truth-table closure and Turing closure of average polynomial time have different measures in EXP

inferredcites →https://doi.org/10.1109/sct.1995.514853openalex-snapshot

A personal view of average-case complexity

inferredcites →https://doi.org/10.1109/sct.1995.514854openalex-snapshot

Towards average-case complexity analysis of NP optimization problems

inferredcites →https://doi.org/10.1137/0213030openalex-snapshot

Quantitative Relativizations of Complexity Classes

inferredcites →https://doi.org/10.1137/0215020openalex-snapshot

Average Case Complete Problems

inferredcites →https://doi.org/10.1137/0216034openalex-snapshot

Expected Computation Time for Hamiltonian Path problem

inferredcites →https://doi.org/10.1137/0220053openalex-snapshot

PP is as Hard as the Polynomial-Time Hierarchy

inferredcites →https://doi.org/10.1137/0222012openalex-snapshot

The Complexity of Malign Measures

inferredcites →https://doi.org/10.1137/0222061openalex-snapshot

Random-Self-Reducibility of Complete Sets

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/174644.174648openalex-snapshot

Instance complexity

inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot

Some connections between nonuniform and uniform complexity classes

inferredcites →https://doi.org/10.21236/ada222821openalex-snapshot

The Emerging Theory of Average-Case Complexity

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.2002.1835openalex-snapshot

New Lowness Results for ZPPNP and Other Complexity Classes

inferred← citeshttps://doi.org/10.1007/11537311_36openalex-snapshot

Average-Case Non-approximability of Optimisation Problems

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-36494-3_20openalex-snapshot

Some Results on Derandomization

inferred← citeshttps://doi.org/10.1007/3-540-46541-3_36openalex-snapshot

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results

inferred← citeshttps://doi.org/10.1007/bfb0055753openalex-snapshot

Mathematical Foundations of Computer Science 1998

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.cosrev.2008.02.001openalex-snapshot

The consequences of eliminating NP solutions

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.18452/9148openalex-snapshot

New lowness results for ZPP (NP) and other complexity classes

showing the first 10 of 11 · page through all 11

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.