Combinatorial PCPs with short proofs
From MaRDI portal
Publication:260390
DOI10.1007/s00037-015-0111-xzbMath1336.68090OpenAlexW2294800560WikidataQ113906245 ScholiaQ113906245MaRDI QIDQ260390
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
Related Items (7)
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
