2023/11/01 by Kothari, Pravesh K., Manohar, Peter · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.00558
We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L \colon \mathbb Fk → \mathbb Fn with distance δ must be at least n ≥ 2^Ω((\fracδ2 k(|\mathbb F|-1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n ≥ Ω(k3) [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 n ≤ 2^O(k1/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 q-query LCCs and LDCs for any constant q ≥ 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].