Tight Lower Bounds for 2-query LCCs over Finite Fields

DOI10.1109/FOCS.2011.28zbMATH Open1292.94184OpenAlexW2010510058MaRDI QIDQ5495035FDOQ5495035

Authors Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, 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)

Cited in

(5)

• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• On the power of relaxed local decoding algorithms
• Sylvester-Gallai type theorems for approximate collinearity
• Improved rank bounds for design matrices and a new proof of Kelly's theorem

This page was built for publication: Tight Lower Bounds for 2-query LCCs over Finite Fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495035)