Composition of low-error 2-query PCPs using decodable PCPs

DOI10.1007/978-3-642-16367-8_21MaRDI QIDQ4933379zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Prahladh Harsha

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

compositionlocally decodablelow soundness errorprobabilistically checkable proofs

Mathematics Subject Classification ID

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

Recommendations

• Composition of low-error 2-query PCPs using decodable PCPs
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Derandomized parallel repetition via structured PCPs
• Two-query PCP with subconstant error

Cites work

• A Parallel Repetition Theorem
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Efficient probabilistically checkable proofs and applications to approximations
• scientific article; zbMATH DE number 1263222 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 3417337 (Why is no real title available?)
• Improved low-degree testing and its applications
• Interactive proofs and the hardness of approximating cliques
• New direct-product testers and 2-query PCPs
• PCP characterizations of NP: towards a polynomially-small error-probability
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Short PCPs with Polylog Query Complexity
• Some optimal inapproximability results
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Sub-constant error probabilistically checkable proof of almost-linear size
• The PCP theorem by gap amplification

Cited in

(7)

• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Two-query PCP with subconstant error
• Short locally testable codes and proofs: a survey in two parts
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Composition of low-error 2-query PCPs using decodable PCPs
• Relaxed locally correctable codes
• Derandomized parallel repetition via structured PCPs

This page was built for publication: Composition of low-error 2-query PCPs using decodable PCPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933379)