An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

We prove that the blocklength 𝑛 of a linear 3-query locally correctable code (LCC) ℒ : F 𝑘 → F 𝑛 with distance 𝛿 must be at least 𝑛 ≥ 2

. In particular, the blocklength of a linear 3query LCC with constant distance over any small field grows exponentially with 𝑘. This improves on the best prior lower bound of 𝑛 ≥ Ω(𝑘 3 ) [AGKM23], 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 binary Reed-Muller codes, which achieve 𝑛 ≤ 2 𝑂(𝑘 1/2 ) . Because there is a 3-query LDC with a strictly subexponential blocklength [Yek08, Efr09], as a corollary we obtain the first strong separation between 𝑞-query LCCs and LDCs for any constant 𝑞 ≥ 3.

Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works [GKM22, HKM23, AGKM23] that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances.

Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations -a structured variant of low-width resolution for XOR formulas from proof complexity [Gri01,Sch08].