Arthur and Merlin as oracles
From MaRDI portal
Publication:649095
DOI10.1007/S00037-011-0015-3zbMATH Open1248.68201OpenAlexW2028556586MaRDI QIDQ649095FDOQ649095
Authors: Venkatesan T. Chakaravarthy, Sambuddha Roy 
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
Recommendations
- Arthur and Merlin as Oracles
- Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Derandomizing Arthur-Merlin games under uniform assumptions
zero-sum gamesboolean matricesconditional derandomizationKarp-Lipton theoremlearning circuitsnear-optimal strategiessymmetric alternation
Cites Work
- On the complexity of succinct zero-sum games
- Hardness vs randomness
- Pseudorandomness for approximate counting and sampling
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- On pseudorandomness and resource-bounded measure
- Derandomizing Arthur-Merlin games using hitting sets
- Simple strategies for large zero-sum games with applications to complexity theory
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Oracles and queries that are sufficient for exact learning
- Title not available (Why is that?)
- Private vs. common random bits in communication complexity
- On sparse approximations to randomized strategies and convex combinations
- Symmetric alternation captures BPP
- More on BPP and the polynomial-time hierarchy
- New Collapse Consequences of NP Having Small Circuits
- Proving SAT does not have small circuits with an application to the two queries problem
- Arthur and Merlin as Oracles
- Oblivious Symmetric Alternation
- If NP has polynomial-size circuits, then MA=AM
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Cited In (5)
- The two queries assumption and Arthur-Merlin classes
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Arthur and Merlin as Oracles
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
This page was built for publication: Arthur and Merlin as oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q649095)
