Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
From MaRDI portal
Publication:2012178
Recommendations
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- On circuit lower bounds from derandomization
- Circuit lower bounds for Merlin-Arthur classes
- Circuit lower bounds for Merlin-Arthur classes
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Lower bounds for the size of nondeterministic circuits
- scientific article; zbMATH DE number 2080255
- Derandomizing Arthur-Merlin games under uniform assumptions
- Tighter connections between derandomization and circuit lower bounds
Cites work
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- Algebraic methods for interactive proof systems
- Arthur and Merlin as oracles
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Circuit-size lower bounds and non-reducibility to sparse sets
- Competing provers yield improved Karp-Lipton collapse results
- Computational Complexity
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- IP = PSPACE
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- On circuit lower bounds from derandomization
- Probabilistic complexity classes and lowness
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Pseudorandomness for approximate counting and sampling
- Some consequences of non-uniform conditions on uniform classes
- Turing machines that take advice
- Two Comments on Targeted Canonical Derandomizers
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cited in
(13)- Arthur and Merlin as oracles
- scientific article; zbMATH DE number 2080255 (Why is no real title available?)
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Circuit lower bounds for Merlin-Arthur classes
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Circuit lower bounds for Merlin-Arthur classes
- Derandomizing Arthur-Merlin games under uniform assumptions
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Holographic Proofs and Derandomization
- Pseudorandomness for approximate counting and sampling
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Derandomizing Arthur-Merlin games using hitting sets
This page was built for publication: Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012178)
