Arthur and Merlin as oracles

DOI10.1007/S00037-011-0015-3MaRDI QIDQ649095zbMATHOpenAlexFDO

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

zbMATH Keywords

zero-sum gamesboolean matricesconditional derandomizationKarp-Lipton theoremlearning circuitsnear-optimal strategiessymmetric alternation

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Arthur and Merlin as Oracles
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Derandomizing Arthur-Merlin games using hitting sets
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hardness vs randomness
• If NP has polynomial-size circuits, then MA=AM
• More on BPP and the polynomial-time hierarchy
• New Collapse Consequences of NP Having Small Circuits
• Oblivious Symmetric Alternation
• On pseudorandomness and resource-bounded measure
• On sparse approximations to randomized strategies and convex combinations
• On the complexity of succinct zero-sum games
• Oracles and queries that are sufficient for exact learning
• Private vs. common random bits in communication complexity
• Proving SAT does not have small circuits with an application to the two queries problem
• Pseudorandomness for approximate counting and sampling
• Simple strategies for large zero-sum games with applications to complexity theory
• Symmetric alternation captures BPP
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

Cited in

(5)

• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Arthur and Merlin as Oracles
• The two queries assumption and Arthur-Merlin classes
• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• Gate elimination: circuit size lower bounds and \#SAT upper bounds

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)