Composition of Low-Error 2-Query PCPs Using Decodable PCPs

DOI10.1007/978-3-642-16367-8_21zbMath1309.68217OpenAlexW3091191389MaRDI QIDQ4933379

Prahladh Harsha, Irit Dinur

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_21

zbMATH Keywords

compositionprobabilistically checkable proofslocally decodablelow soundness error

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Randomized algorithms (68W20)

Related Items

Unnamed Item ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sub-constant error probabilistically checkable proof of almost-linear size
• Improved low-degree testing and its applications
• PCP characterizations of NP
• Proof verification and the hardness of approximation problems
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Short PCPs with Polylog Query Complexity
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• 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
• Some optimal inapproximability results
• 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