@inproceedings{gopi2017lower,
author = {Gopi, Sivakanth and Bhattacharyya, Arnab and Tal, Avishay},
title = {Lower bounds for 2-query LCCs over large alphabet},
booktitle = {RANDOM 2017},
year = {2017},
month = {January},
abstract = {A locally correctable code (LCC) is an error correcting code that allows
correction of any arbitrary coordinate of a corrupted codeword by querying only
a few coordinates. We show that any [\em zero-error] $2$-query locally
correctable code $\mathcal[C]: \[0,1\]^k \to Σ^n$ that can correct a
constant fraction of corrupted symbols must have $n \geq \exp(k/\log|Σ|)$.
We say that an LCC is zero-error if there exists a non-adaptive corrector
algorithm that succeeds with probability $1$ when the input is an uncorrupted
codeword. All known constructions of LCCs are zero-error.

Our result is tight upto constant factors in the exponent. The only previous
lower bound on the length of 2-query LCCs over large alphabet was
$Ω\left((k/\log|Σ|)^2\right)$ due to Katz and Trevisan (STOC 2000).
Our bound implies that zero-error LCCs cannot yield $2$-server private
information retrieval (PIR) schemes with sub-polynomial communication. Since
there exists a $2$-server PIR scheme with sub-polynomial communication (STOC
2015) based on a zero-error $2$-query locally decodable code (LDC), we also
obtain a separation between LDCs and LCCs over large alphabet.

For our proof of the result, we need a new decomposition lemma for directed
graphs that may be of independent interest. Given a dense directed graph $G$,
our decomposition uses the directed version of Szemerédi regularity lemma due
to Alon and Shapira (STOC 2003) to partition almost all of $G$ into a constant
number of subgraphs which are either edge-expanding or empty.},
url = {http://approjects.co.za/?big=en-us/research/publication/lower-bounds-for-2-query-lccs-over-large-alphabet/},
}