Arthur and Merlin as oracles
From MaRDI portal
Publication:649095
DOI10.1007/s00037-011-0015-3zbMath1248.68201OpenAlexW2028556586MaRDI QIDQ649095
Sambuddha Roy, Venkatesan T. Chakaravarthy
Publication date: 30 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0015-3
zero-sum gamesboolean matricesconditional derandomizationKarp-Lipton theoremlearning circuitsnear-optimal strategiessymmetric alternation
Related Items
Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Cites Work
- Unnamed Item
- If NP has polynomial-size circuits, then MA=AM
- Derandomizing Arthur-Merlin games using hitting sets
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- On the complexity of succinct zero-sum games
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Private vs. common random bits in communication complexity
- Symmetric alternation captures BPP
- On sparse approximations to randomized strategies and convex combinations
- Hardness vs randomness
- More on BPP and the polynomial-time hierarchy
- Oracles and queries that are sufficient for exact learning
- Pseudorandomness for approximate counting and sampling
- Proving SAT does not have small circuits with an application to the two queries problem
- Simple strategies for large zero-sum games with applications to complexity theory
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Arthur and Merlin as Oracles
- New Collapse Consequences of NP Having Small Circuits
- Oblivious Symmetric Alternation
- On pseudorandomness and resource-bounded measure
