Random Debaters and the Hardness of Approximating Stochastic Functions

DOI10.1137/S0097539793260738MaRDI QIDQ4337648zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

approximation algorithmscomplexity theoryprobabilistic gamesPSPACEproof systems

Mathematics Subject Classification ID

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

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

Cited in

(8)

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

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)