Relations between average-case and worst-case complexity
From MaRDI portal
Publication:927398
DOI10.1007/s00224-007-9071-0zbMath1140.68023OpenAlexW1966017288MaRDI QIDQ927398
Publication date: 6 June 2008
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-9071-0
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Average-case intractability vs. worst-case intractability
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- NP is as easy as detecting unique solutions
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Average case completeness
- On the theory of average case complexity
- Highly resilient correctors for polynomials
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Pseudorandomness for approximate counting and sampling
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Average Case Complete Problems
- Separating Nondeterministic Time Complexity Classes
- Tally languages and complexity classes
- Easiness assumptions and hardness tests: Trading time for zero error
This page was built for publication: Relations between average-case and worst-case complexity
