ECCC-Report TR11-054https://eccc.weizmann.ac.il/report/2011/054Comments and Revisions published for TR11-054en-usWed, 13 Apr 2011 02:48:59 +0300
Paper TR11-054
| Tight lower bounds for 2-query LCCs over finite fields |
Arnab Bhattacharyya,
Zeev Dvir,
Shubhangi Saraf,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2011/054A 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.Wed, 13 Apr 2011 02:48:59 +0300https://eccc.weizmann.ac.il/report/2011/054