Arthur and Merlin as Oracles

DOI10.1007/978-3-540-85238-4_18MaRDI QIDQ3599130zbMATH OpenOpenAlexFDO

Authors Venkatesan T. Chakaravarthy, Sambuddha Roy

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_18

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Applications of game theory (91A80)

Recommendations

• Arthur and Merlin as oracles
• Derandomizing Arthur-Merlin games using hitting sets
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Derandomizing Arthur-Merlin games under uniform assumptions
• scientific article; zbMATH DE number 4050983

Cites work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Derandomizing Arthur-Merlin games using hitting sets
• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hardness vs randomness
• scientific article; zbMATH DE number 3867093 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• On sparse approximations to randomized strategies and convex combinations
• On the complexity of succinct zero-sum games
• Optimal orientations of cells in slicing floorplan designs
• Private vs. common random bits in communication complexity
• Pseudorandomness for approximate counting and sampling
• Simple strategies for large zero-sum games with applications to complexity theory

Cited in

(1)

• Arthur and Merlin as oracles

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 Q3599130)