Random Debaters and the Hardness of Approximating Stochastic Functions

DOI10.1137/S0097539793260738zbMATH Open0874.68125DBLPjournals/siamcomp/CondonFLS97OpenAlexW2165318736WikidataQ57567604 ScholiaQ57567604MaRDI QIDQ4337648FDOQ4337648

Authors: Anne Condon, Joan Feigenbaum, C. Lund, Peter W. Shor 

Publication date: 26 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793260738

Recommendations

• scientific article; zbMATH DE number 1332658
• Efficient Probabilistically Checkable Debates
• The complexity of debate checking
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE

zbMATH Keywords

approximation algorithmscomplexity theoryprobabilistic gamesPSPACEproof systems

Mathematics Subject Classification ID

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

Cited In (8)

• Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies
• Trainyard is NP-hard
• Complexity limitations on one-turn quantum refereed games
• Efficient Probabilistically Checkable Debates
• A PCP characterization of AM
• A PCP theorem for interactive proofs and applications
• A toolbox for barriers on interactive oracle proofs
• Complexity and approximability of quantified and stochastic constraint satisfaction problems

This page was built for publication: Random Debaters and the Hardness of Approximating Stochastic Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337648)