Derandomized parallel repetition via structured PCPs
From MaRDI portal
Publication:645129
DOI10.1007/s00037-011-0013-5zbMath1255.68068OpenAlexW2146392217MaRDI QIDQ645129
Publication date: 8 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0013-5
Related Items
Derandomized parallel repetition via structured PCPs, Combinatorial PCPs with efficient verifiers, Direct Sum Testing, Combinatorial PCPs with short proofs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Derandomized parallel repetition via structured PCPs
- PCP characterizations of NP: toward a polynomially-small error-probability
- Ramanujan graphs
- Optimization, approximation, and complexity classes
- Improved low-degree testing and its applications
- Nearly-linear size holographic proofs
- Proof verification and the hardness of approximation problems
- Sub-Constant Error Low Degree Test of Almost-Linear Size
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Combinatorial PCPs with Efficient Verifiers
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- New direct-product testers and 2-query PCPs
- Efficient probabilistically checkable proofs and applications to approximations
- Clustering in the Boolean Hypercube in a List Decoding Regime
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The PCP theorem by gap amplification
- Sound 3-Query PCPPs Are Long
