Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-054 | 13th April 2011 01:47

Tight lower bounds for 2-query LCCs over finite fields


Authors: Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
Publication: 13th April 2011 02:48
Downloads: 3282


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 $\delta$ of the
coordinates are corrupted. LCC's 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^{\Omega(\delta 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^{\Omega(\delta 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.

We also obtain, as corollaries of our main theorem, new results in incidence geometry
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

ISSN 1433-8092 | Imprint