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 gamesproof systemsPSPACE

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

(10)

• Trainyard is NP-hard
• A PCP theorem for interactive proofs and applications
• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• A PCP characterization of AM
• Efficient Probabilistically Checkable Debates
• scientific article; zbMATH DE number 1332658 (Why is no real title available?)
• Complexity limitations on one-turn quantum refereed games
• A toolbox for barriers on interactive oracle proofs
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
• Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

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)