Short Locally Testable Codes and Proofs
DOI10.1007/978-3-642-22670-0_25zbMath1309.68220MaRDI QIDQ3088191
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
derandomization; probabilistically checkable proofs; error-correcting codes; locally testable codes; locally decodable codes; private information retrieval; self-correction; low-degree tests
68Q25: Analysis of algorithms and problem complexity
68Q60: Specification and verification (program logics, model checking, etc.)
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94B60: Other types of codes
68W20: Randomized algorithms
Related Items
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
