Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
From MaRDI portal
Publication:2012178
DOI10.1007/s00037-014-0095-yzbMath1371.68094OpenAlexW2175404758MaRDI QIDQ2012178
Dieter van Melkebeek, Bariş Aydinlioǧlu
Publication date: 28 July 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0095-y
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Natural Proofs versus Derandomization ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
Cites Work
- Unnamed Item
- Unnamed Item
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Arthur and Merlin as oracles
- Turing machines that take advice
- Some consequences of non-uniform conditions on uniform classes
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Probabilistic complexity classes and lowness
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Competing provers yield improved Karp-Lipton collapse results
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Pseudorandomness for approximate counting and sampling
- In a World of P=BPP
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit-size lower bounds and non-reducibility to sparse sets
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Two Comments on Targeted Canonical Derandomizers
- Computational Complexity
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
