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 Sigma^n$ that can correct a constant fraction of corrupted symbols must have $n geq exp(k/log|Sigma|)$. 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. 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 $Omegaleft((k/log|Sigma|)^2right)$ 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 Szemeru0027edi 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. |
Year | Venue | DocType |
---|---|---|
2016 | international workshop and international workshop on approximation, randomization, and combinatorial optimization. algorithms and techniques | Journal |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arnab Bhattacharyya | 1 | 214 | 27.99 |
Sivakanth Gopi | 2 | 25 | 5.63 |