Combinatorial PCPs with short proofs

DOI10.1007/s00037-015-0111-xzbMath1336.68090OpenAlexW2294800560WikidataQ113906245 ScholiaQ113906245MaRDI QIDQ260390

Or Meir

Publication date: 21 March 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0111-x

zbMATH Keywords

combinatorial PCPPCP of proximityprobabilistically checkable proof (PCP)

Mathematics Subject Classification ID

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

Related Items

Succinct non-interactive arguments via linear interactive proofs ⋮ Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Relaxed Locally Correctable Codes ⋮ Shorter arithmetization of nondeterministic computations ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomized parallel repetition via structured PCPs
• Optimization, approximation, and complexity classes
• On decoding by error location and dependent sets of error positions
• Nearly-linear size holographic proofs
• IP = PSPACE Using Error-Correcting Codes
• Expander codes
• Proof verification and the hardness of approximation problems
• A Combination of Testability and Decodability by Tensor Products
• Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
• Locally testable codes and PCPs of almost-linear length
• Robust Local Testability of Tensor Products of LDPC Codes
• Short PCPs with Polylog Query Complexity
• Composition of Semi-LTCs by Two-Wise Tensor Products
• Probabilistic checking of proofs
• Relations Among Complexity Measures
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• Combinatorial PCPs with Efficient Verifiers
• Robust locally testable codes and products of codes
• The complexity of theorem-proving procedures
• 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
• Sound 3-Query PCPPs Are Long
• Property testing in bounded degree graphs

This page was built for publication: Combinatorial PCPs with short proofs