Abstract: A locally correctable code (LCC) is an error correcting code where one can recover any symbol of the original codeword by querying only a small number of randomly chosen symbols from the received corrupted codeword.
In this talk, we present a proof that the blocklength $n$ of a linear $3$-query LCC $C: \{0,1\}^k \rightarrow \{0,1\}^n$ must be at least $\exp{(k^{1/8})}$, i.e., it grows exponentially with $k$. This improves on the prior best lower bound of $k^3$ shown in our recent work, which holds even for the weaker setting of $3$-query locally decodable codes (LDCs), and comes close to matching the best-known construction of $3$-query LCCs based on Reed—Muller codes, which achieve a blocklength of $n = \exp{(\sqrt{k})}$. Because there is a $3$-query LDC with a strictly subexponential blocklength, as a corollary we obtain the first separation between $q$-query LCCs and LDCs for any constant $q$.
We subsequently show that any “design $3$-LCC”, an LCC with a parity check matrix that is a block design, must have blocklength at least $2^{(1-o(1)) \sqrt{k}}$. As Reed—Muller codes are design $3$-LCCs with blocklength $n = 2^{2 \sqrt{2k}}$, this is tight up to a factor of $2 \sqrt{2}$ in the exponent, and as a corollary resolves the Hamada conjecture for $4$-designs up to this constant factor. For nonlinear LCCs, we give a generalization of our approach that proves a superpolynomial lower bound of $k^{\log k}$, improving on the prior best lower bound of $k^3$.
Based on joint work with Pravesh K. Kothari.