Derandomized parallel repetition via structured PCPs

DOI10.1007/s00037-011-0013-5zbMath1255.68068OpenAlexW2146392217MaRDI QIDQ645129

Or Meir, Irit Dinur

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

zbMATH Keywords

direct productPCPde-Bruijnderandomized parallel repetitiondirect product testlow error

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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