Dense Locally Testable Codes Cannot Have Constant Rate and Distance
From MaRDI portal
Publication:3088121
DOI10.1007/978-3-642-22935-0_43zbMath1343.94103arXiv1012.2738MaRDI 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
Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs, 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}\), Quantum Locally Testable Codes
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