scientific article; zbMATH DE number 1332658

MaRDI QIDQ4259979zbMATH OpenFDO

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

Publication date 7 September 1999

zbMATH Keywords

probabilistically checkable debate systems

Mathematics Subject Classification ID

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

Cited in

(9)

• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• 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

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)