Tight Lower Bounds for 2-query LCCs over Finite Fields

DOI10.1109/FOCS.2011.28zbMath1292.94184OpenAlexW2010510058MaRDI QIDQ5495035

Zeev Dvir, Amir Shpilka, Arnab Bhattacharyya, Shubhangi Saraf

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.28

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Other types of codes (94B60) Finite geometry and special incidence structures (51E99)

Related Items

Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM