PCPs with small soundness error
Author:
Open Access
- 1 September 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 39 (3) , 41-57
Abstract
The soundness error of a PCP verifier is the probability (usually denoted ε) that the verifier accepts an incorrect input. We are interested in the smallest possible values of ε for which the PCP theorem holds, and in particular whether the theorem holds when ε is an inverse polynomial function of the input length. We discuss the 'sliding scale conjecture' of [BGLR93, LY94] and related questions. We then sketch some of the existing approaches and constructions of PCPs with sub-constant soundness error.Keywords
This publication has 16 references indexed in Scilit:
- The PCP theorem by gap amplificationJournal of the ACM, 2007
- Assignment Testers: Towards a Combinatorial Proof of the PCP TheoremSIAM Journal on Computing, 2006
- Robust PCPs of Proximity, Shorter PCPs, and Applications to CodingSIAM Journal on Computing, 2006
- PCP characterizations of NP1999
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Improved low-degree testing and its applications1997
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Impossibility results for recycling random bits in two-prover proof systems1995