Arthur and Merlin as Oracles
From MaRDI portal
Publication:3599130
DOI10.1007/978-3-540-85238-4_18zbMath1173.68524OpenAlexW1485175394MaRDI QIDQ3599130
Sambuddha Roy, Venkatesan T. Chakaravarthy
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Derandomizing Arthur-Merlin games using hitting sets
- 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
- On sparse approximations to randomized strategies and convex combinations
- Hardness vs randomness
- Pseudorandomness for approximate counting and sampling
- Simple strategies for large zero-sum games with applications to complexity theory
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Optimal orientations of cells in slicing floorplan designs
This page was built for publication: Arthur and Merlin as Oracles
