Combinatorial PCPs with short proofs

DOI10.1007/s00037-015-0111-xzbMath1336.68090WikidataQ113906245 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 PCP; PCP of proximity; probabilistically checkable proof (PCP)

Mathematics Subject Classification ID

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

Related Items

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

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