Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. (Q519967)

A linear Locally Correctable Code (LCC) over the finite field with \(p\) elements is a subspace of \(\mathbb F_p^n\) with the property that given a vector \(z\) that disagrees with an element of the code \(y\) in at most \(\delta n\) coordinates and an index \(i\), one can recover \(y_i\) with high probability by reading at most \(q\) coordinates of \(z\). These codes are a strengthening of the notion of Locally Decodable Codes (LDC). The authors give a distinction between LDCs and LCCs over finite fields of prime order with \(q=2\), by proving a lower bound of the form \(p^{\Omega(d \delta)}\) on the length of linear \(2\)-query LCCs over \(F_p\) that encode messages of length \(d\). The proof is combinatorial in nature and gives two corollaries in incidence geometry. Namely, the authors give an improvement to the Sylvester-Gallai Theorem over finite fields and a new analog of Beck's Theorem over finite fields. The paper concludes with an appendix, written by Sergey Yekhanin, which contains a proof that there do exist linear LCCs of size \(2^{O(d)}.\)