Towards lower bounds on locally testable codes via density arguments
From MaRDI portal
Publication:693000
DOI10.1007/S00037-012-0042-8zbMATH Open1302.94064OpenAlexW228023874MaRDI QIDQ693000FDOQ693000
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
Recommendations
- Dense locally testable codes cannot have constant rate and distance
- Locally Testable Codes Require Redundant Testers
- High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
- Corruption and Recovery-Efficient Locally Decodable Codes
- High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Cites Work
- Title not available (Why is that?)
- Proof verification and the hardness of approximation problems
- Locally testable codes and PCPs of almost-linear length
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Locally Testable Cyclic Codes
- Bounds on 2-query locally testable codes with affine tests
- Bounds on locally testable codes with unique tests
- On 2-Query Codeword Testing with Near-Perfect Completeness
- Some 3CNF Properties Are Hard to Test
- Bounds on \(2\)-query codeword testing
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- A Parallel Repetition Theorem
- Symmetric LDPC codes and local testing
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Title not available (Why is that?)
- Algebraic property testing: the role of invariance
- Title not available (Why is that?)
- Testing Reed–Muller Codes
- Combinatorial construction of locally testable codes
- The PCP theorem by gap amplification
- Low Rate Is Insufficient for Local Testability
- Locally testable vs. locally decodable codes
- High-rate codes with sublinear-time decoding
- Lower bounds for linear locally decodable codes and private information retrieval
- New direct-product testers and 2-query PCPs
- Clustering in the Boolean Hypercube in a List Decoding Regime
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- A quadratic lower bound for three-query linear locally decodable codes over any field
- Title not available (Why is that?)
- Limitation on the Rate of Families of Locally Testable Codes
- Locally Testable Codes Require Redundant Testers
- Towards lower bounds on locally testable codes via density arguments
Cited In (8)
- Locally Testable Codes Require Redundant Testers
- Towards lower bounds on locally testable codes via density arguments
- On coset leader graphs of structured linear codes
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Locally testable codes with constant rate, distance, and locality
- Locally testable codes and PCPs of almost-linear length
- Limitation on the Rate of Families of Locally Testable Codes
This page was built for publication: Towards lower bounds on locally testable codes via density arguments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693000)
