Short Locally Testable Codes and Proofs

DOI10.1007/978-3-642-22670-0_25zbMath1309.68220OpenAlexW158403657MaRDI QIDQ3088191

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_25

zbMATH Keywords

derandomizationprobabilistically checkable proofserror-correcting codeslocally testable codeslocally decodable codesprivate information retrievalself-correctionlow-degree tests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60) Randomized algorithms (68W20)

Related Items

Locally Decodable Codes for Edit Distance, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, The tensor product of two good codes is not necessarily robustly testable, On the rectangle method in proofs of robustness of tensor products, Composition of semi-LTCs by two-wise tensor products, General constructions for information-theoretic private information retrieval, Limitation on the Rate of Families of Locally Testable Codes, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Short Locally Testable Codes and Proofs, Testing algebraic geometric codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Lower bounds for linear locally decodable codes and private information retrieval
• Self-testing/correcting with applications to numerical problems
• On the power of multi-prover interactive protocols
• Fully parallelized multi-prover protocols for NEXP-time
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Efficient checking of polynomials and proofs and the hardness of approximation problems
• Improved non-approximability results
• Nearly-linear size holographic proofs
• Fast approximate PCPs
• Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
• Short Locally Testable Codes and Proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Private information retrieval
• On the efficiency of local decoding procedures for error-correcting codes
• Locally testable codes and PCPs of almost-linear length
• Combinatorial Construction of Locally Testable Codes
• Some 3CNF properties are hard to test
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Short PCPs with Polylog Query Complexity
• Probabilistic checking of proofs
• Algebraic methods for interactive proof systems
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Computationally Sound Proofs
• Upper bound on the communication complexity of private information retrieval
• Robust Characterizations of Polynomials with Applications to Program Testing
• Property Testing of Massively Parametrized Problems – A Survey
• Combinatorial PCPs with Efficient Verifiers
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• 3-query locally decodable codes of subexponential length
• Efficient probabilistically checkable proofs and applications to approximations
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Locally Testable Codes Require Redundant Testers
• Some optimal inapproximability results
• 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
• Computational Complexity
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Small PCPs with low query complexity