Towards lower bounds on locally testable codes via density arguments
From MaRDI portal
Publication:693000
DOI10.1007/s00037-012-0042-8zbMath1302.94064MaRDI QIDQ693000
Michael Viderman, Eli Ben-Sasson
Publication date: 7 December 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0042-8
Related Items
Towards lower bounds on locally testable codes via density arguments, On coset leader graphs of structured linear codes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounds on 2-query locally testable codes with affine tests
- Towards lower bounds on locally testable codes via density arguments
- Lower bounds for linear locally decodable codes and private information retrieval
- Bounds on locally testable codes with unique tests
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Proof verification and the hardness of approximation problems
- Locally testable codes and PCPs of almost-linear length
- Testing Reed–Muller Codes
- Locally Testable Cyclic Codes
- Combinatorial Construction of Locally Testable Codes
- Low Rate Is Insufficient for Local Testability
- Locally Testable vs. Locally Decodable Codes
- A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Limitation on the Rate of Families of Locally Testable Codes
- Symmetric LDPC Codes and Local Testing
- New direct-product testers and 2-query PCPs
- Clustering in the Boolean Hypercube in a List Decoding Regime
- Locally Testable Codes Require Redundant Testers
- High-rate codes with sublinear-time decoding
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- On 2-Query Codeword Testing with Near-Perfect Completeness
- Some 3CNF Properties Are Hard to Test
- 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
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
