Tight Lower Bounds for 2-query LCCs over Finite Fields

DOI10.1109/FOCS.2011.28MaRDI QIDQ5495035zbMATH OpenOpenAlexFDO

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

(6)

• Sylvester-Gallai type theorems for approximate collinearity
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• On the power of relaxed local decoding algorithms
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• 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)