New direct-product testers and 2-query PCPs
Authors:
Open Access
- 31 May 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 131-140
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- PCPs with small soundness errorACM SIGACT News, 2008
- The PCP theorem by gap amplificationJournal of the ACM, 2007
- Error Reduction by Parallel Repetition—A Negative ResultCombinatorica, 2002
- Spot-CheckersJournal of Computer and System Sciences, 2000
- Two-Prover Protocols---Low Error at Affordable RatesSIAM Journal on Computing, 2000
- A Combinatorial Consistency Lemma with Application to Proving the PCP TheoremSIAM Journal on Computing, 2000
- A Parallel Repetition TheoremSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Towards the parallel repetition conjectureTheoretical Computer Science, 1996