Short Locally Testable Codes and Proofs: A Survey in Two Parts

DOI10.1007/978-3-642-16367-8_6zbMath1309.68218OpenAlexW189554415MaRDI QIDQ4933364

Oded Goldreich

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_6

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) Theory of error-correcting codes and error-detecting codes (94B99) Randomized algorithms (68W20) Complexity of proofs (03F20)

Related Items

Quantum Locally Testable Codes, Local Testing of Lattices, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Non-interactive proofs of proximity, On the Power of Relaxed Local Decoding Algorithms, Unnamed Item

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}\)
• 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
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Combinatorial PCPs with Efficient Verifiers
• 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
• Computational Complexity
• The PCP theorem by gap amplification
• 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