Derandomized parallel repetition via structured PCPs
From MaRDI portal
Publication:645129
DOI10.1007/S00037-011-0013-5zbMATH Open1255.68068OpenAlexW2146392217MaRDI QIDQ645129FDOQ645129
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
Recommendations
Cites Work
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Optimization, approximation, and complexity classes
- Nearly-linear size holographic proofs
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Title not available (Why is that?)
- Interactive proofs and the hardness of approximating cliques
- Title not available (Why is that?)
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Combinatorial PCPs with Efficient Verifiers
- 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
- Derandomized parallel repetition via structured PCPs
- Ramanujan graphs
- Title not available (Why is that?)
- A Parallel Repetition Theorem
- Efficient probabilistically checkable proofs and applications to approximations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved low-degree testing and its applications
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- PCP characterizations of NP: toward a polynomially-small error-probability
- Sub-Constant Error Low Degree Test of Almost-Linear Size
- New direct-product testers and 2-query PCPs
- Clustering in the Boolean Hypercube in a List Decoding Regime
- Sound 3-Query PCPPs Are Long
Cited In (6)
This page was built for publication: Derandomized parallel repetition via structured PCPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645129)
