scientific article; zbMATH DE number 1332658

zbMATH Open0924.68177MaRDI QIDQ4259979FDOQ4259979

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

Publication date: 7 September 1999

Title of this publication is not available (Why is that?)

Recommendations

• Random Debaters and the Hardness of Approximating Stochastic Functions
• Efficient Probabilistically Checkable Debates
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE

zbMATH Keywords

probabilistically checkable debate systems

Mathematics Subject Classification ID

Cited In (9)

• Quantified maximum satisfiability
• Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies
• Complexity limitations on one-turn quantum refereed games
• A nonapproximability result for finite function generation
• Efficient Probabilistically Checkable Debates
• A PCP characterization of AM
• Constant-round interactive proofs for delegating computation
• A PCP theorem for interactive proofs and applications
• Complexity and approximability of quantified and stochastic constraint satisfaction problems

This page was built for publication:

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