Locally Correctable Codes (LCCs) are error correcting codes in which one can recover the values of a possibly corrupted codeword position using a small number of queries to the other positions. Such codes include Reed Muller codes and Hadamard codes and they play an important part in many results in theoretical computer science, including in hardness of approximation, derandomization and PCPs. It is a major open problem to understand the power and limitations of such codes. Until now, the best lower bound on the encoding length of constant query codes with more than 2 queries was quadratic. This was also the case for *linear* codes.
We prove that 3-query linear LCCs over the field of real numbers require encoding length which is super quadratic (d^{2.001}). Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that $n > d^{2.001}$. While a modest improvement on the known bounds, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well.
Joint work with Shubhangi Saraf (Rutgers) and Avi Wigderson (IAS).
Copyright. All Rights Reserved.