A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
From MaRDI portal
Publication:3588449
DOI10.1007/978-3-642-15369-3_57zbMath1306.94112MaRDI QIDQ3588449
Publication date: 10 September 2010
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_57
94B05: Linear codes (general theory)
94B65: Bounds on codes
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94B35: Decoding
Related Items
Locality via Partially Lifted Codes, Lifted Multiplicity Codes and the Disjoint Repair Group Property, Towards lower bounds on locally testable codes via density arguments, Hermitian-lifted codes