Relations between average-case and worst-case complexity

DOI10.1007/s00224-007-9071-0zbMath1140.68023OpenAlexW1966017288MaRDI QIDQ927398

N. V. Vinodchandran, A. Pavan

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

zbMATH Keywords

Arthur-Merlin gamesAverage-case complexityWorst-case complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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