Efficient Probabilistically Checkable Debates

DOI10.1007/978-3-642-22935-0_44MaRDI QIDQ3088122zbMATH OpenOpenAlexFDO

Authors Andrew Drucker

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://www.pure.ed.ac.uk/ws/files/19272854/Drucker_2011_Efficient_Probabilistically_Checkabe_Debates.pdf

zbMATH Keywords

PCPsPCPPsprobabilistically checkable debates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Recommendations

• scientific article; zbMATH DE number 1332658
• Probabilistically Checkable Arguments
• Rational arguments: single round delegation with sublinear verification
• On the concrete efficiency of probabilistically-checkable proofs
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
• The complexity of debate checking
• Fast approximate probabilistically checkable proofs
• Efficient, verified checking of propositional proofs
• Probabilistically checkable proofs and codes

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1332658 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Alternation
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Beyond NP
• Coding for interactive communication
• Complete sets and the polynomial-time hierarchy
• IP = PSPACE
• Infeasibility of instance compression and succinct PCPs for NP
• Linear-time encodable and decodable error-correcting codes
• Non-deterministic exponential time has two-prover interactive protocols
• Proof verification and the hardness of approximation problems
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Robust locally testable codes and products of codes
• The PCP theorem by gap amplification
• The polynomial-time hierarchy
• Towards coding for maximum errors in interactive communication

Cited in

(5)

• Credible debate equilibria
• Debates with small transparent quantum verifiers
• Constant-round interactive proofs for delegating computation
• The complexity of debate checking
• A PCP theorem for interactive proofs and applications

This page was built for publication: Efficient Probabilistically Checkable Debates

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