Paper Info
Title
Tight Lower Bounds for 2-query LCCs over Finite Fields
Abstract
A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction Î麓 of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^{Ω(Î麓d)} on the length of linear 2-query LCCs over $\F_p$, that encode messages of length d. Our bound improves over the known bound of $2^{Ω(Î麓d)} \cite{GKST06, KdW04, DS07} which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields \cite{SS10} and the second is a new analog of Beck's theorem over finite fields.
Year
DOI
Venue
2011
10.1109/FOCS.2011.28
Foundations of Computer Science
Keywords
DocType
Volume
sylvester-gallai theorem,2-query lccs,finite fields,finite field,stronger form,new analog,correctable code,new incidence geometry result,2-query ldcs,form p,main theorem,tight lower bounds,additives,vectors,decoding,computer science,galois fields,geometry
Journal
18
ISSN
ISBN
Citations 
0272-5428
978-1-4577-1843-4
6
PageRank 
References 
Authors
0.55
10
4
Name
Order
Citations
PageRank
Arnab Bhattacharyya121427.99
Zeev Dvir243730.85
Amir Shpilka3109564.27
Shubhangi Saraf426324.55