Combinatorial PCPs with efficient verifiers

DOI10.1007/s00037-014-0080-5zbMath1318.68087OpenAlexW2061595984MaRDI QIDQ483706

Or Meir

Publication date: 17 December 2014

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

Full work available at URL: https://doi.org/10.1007/s00037-014-0080-5

zbMATH Keywords

probabilistically checkable proofscombinatorial PCPPCP of proximity

Mathematics Subject Classification ID

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

Related Items

Erasures versus errors in local decoding and property testing ⋮ Combinatorial PCPs with efficient verifiers ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial PCPs with efficient verifiers
• Derandomized parallel repetition via structured PCPs
• Non-deterministic exponential time has two-prover interactive protocols
• Nearly-linear size holographic proofs
• Linear-time encodable and decodable error-correcting codes
• Proof verification and the hardness of approximation problems
• Short PCPs with Polylog Query Complexity
• Universal Arguments and their Applications
• Probabilistic checking of proofs
• Combinatorial PCPs with Efficient Verifiers
• 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

This page was built for publication: Combinatorial PCPs with efficient verifiers