An Exponential Lower bound on Three Query, Linear Locally Correctable Codes

I will prove that the block length of every linear 3-query Locally Correctable Code (LCC) with a constant distance over any small field grows exponentially with k, the dimension of the code. This result gives the first separation between LCCs and LDCs where it is known that 3-query codes of subexponential length exist. (A q-query LCC is a code where every coordinate of a codeword can be recovered whp from q queries into a corrupted codeword provided the fraction of errors is a small (but positive) constant. In contrast, an LDC only allows for recovery of some linearly independent set k

of the n coordinates.)

My goal is to explain the following conceptual idea in the talk: You can often take an arbitrary combinatorial object (such as a local code with some rate) and associate it with a family of satisfiable XOR formulas (e.g., encoding that the local checks "work"). Proving the unsatisfiability of a randomly chosen member of this family yields the impossibility of the existence of this combinatorial object (in our case a code with the given rate.) We might naturally turn to the large body of tools for analyzing random XOR formulas. Unfortunately, in our setting, the transformation from codes produces formulas on n

variables using roughly only polylog n bits of randomness so one cannot hope for a proof of the unsatisfiability of the formulas via naive probabilistic analysis.

The new "ace up our sleeve" is a class of spectral methods that can prove even such "randomness-starved" formulas unsatisfiable. These spectral methods are based on variants of "Kikuchi matrices" for which, there is now an emerging set of tools for analyzing the spectral properties via tight connections to the "local" combinatorial structure of the target XOR formula.

Based on joint work with Peter Manohar (CMU).