Dense Locally Testable Codes Cannot Have Constant Rate and Distance
From MaRDI portal
Publication:3088121
DOI10.1007/978-3-642-22935-0_43zbMath1343.94103arXiv1012.2738OpenAlexW2138684901MaRDI QIDQ3088121
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.2738
Related Items (5)
Quantum Locally Testable Codes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On coset leader graphs of structured linear codes ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
Cites Work
- Locally testable codes and PCPs of almost-linear length
- Combinatorial Construction of Locally Testable Codes
- Simple PCPs with poly-log rate and query complexity
- Locally Testable Codes Require Redundant Testers
- The PCP theorem by gap amplification
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: Dense Locally Testable Codes Cannot Have Constant Rate and Distance