Derandomized Parallel Repetition via Structured PCPs
Open Access
- 26 May 2011
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 20 (2) , 207-327
Abstract
No abstract availableKeywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite CliqueSIAM Journal on Computing, 2006
- Improved Low-Degree Testing and its ApplicationsCombinatorica, 2003
- 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
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Efficient probabilistically checkable proofs and applications to approximations1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Ramanujan graphsCombinatorica, 1988