Efficient Probabilistically Checkable Debates
From MaRDI portal
Publication:3088122
DOI10.1007/978-3-642-22935-0_44zbMath1343.68026OpenAlexW2295591259MaRDI QIDQ3088122
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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)
Related Items (2)
A PCP theorem for interactive proofs and applications ⋮ Constant-Round Interactive Proofs for Delegating Computation
Cites Work
- Infeasibility of instance compression and succinct PCPs for NP
- Non-deterministic exponential time has two-prover interactive protocols
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Linear-time encodable and decodable error-correcting codes
- Coding for interactive communication
- Proof verification and the hardness of approximation problems
- Beyond NP
- Alternation
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Random Debaters and the Hardness of Approximating Stochastic Functions
- Towards coding for maximum errors in interactive communication
- Robust locally testable codes and products of codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- The PCP theorem by gap amplification
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient Probabilistically Checkable Debates
