TR11-054 Authors: Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Publication: 13th April 2011 02:48

Downloads: 3282

Keywords:

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

fields.