Combinatorial PCPs with short proofs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1405671 (Why is no real title available?)
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- A combination of testability and decodability by tensor products
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Combinatorial PCPs with Efficient Verifiers
- Composition of Semi-LTCs by Two-Wise Tensor Products
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Derandomized parallel repetition via structured PCPs
- Expander codes
- IP = PSPACE using error-correcting codes
- Locally testable codes and PCPs of almost-linear length
- Nearly-linear size holographic proofs
- On decoding by error location and dependent sets of error positions
- Optimization, approximation, and complexity classes
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Property testing in bounded degree graphs
- Relations Among Complexity Measures
- Robust Local Testability of Tensor Products of LDPC Codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Robust locally testable codes and products of codes
- Short PCPs with Polylog Query Complexity
- Sound 3-query PCPPs are long
- Tensor products of weakly smooth codes are robust
- The PCP theorem by gap amplification
- The complexity of theorem-proving procedures
Cited in
(16)- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Shorter arithmetization of nondeterministic computations
- Short PCPs with Polylog Query Complexity
- scientific article; zbMATH DE number 7283890 (Why is no real title available?)
- Erasures versus errors in local decoding and property testing
- Relaxed locally correctable codes
- Erasures vs. errors in local decoding and property testing
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Succinct non-interactive arguments via linear interactive proofs
- Relaxed locally correctable codes
- VC-dimensions of short Presburger formulas
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- On Dinur’s proof of the PCP theorem
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Combinatorial PCPs with efficient verifiers
- Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
This page was built for publication: Combinatorial PCPs with short proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260390)
