Lower bounds for 2-query LCCs over large alphabet - Gopi, Sivakanth; Bhattacharyya, Arnab; Tal, Avishay (RANDOM 2017, 2017)
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 [zero-error] 2-query locally correctable code [C]: \[0,1\]^k → Σ^n that can correct a constant fraction of corrupted symbols must have n ≥ (k/|Σ|). 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 Ω((k/|Σ|)^2) 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.