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

by Pravesh Kothari and Peter Manohar

#### Oded's comments

The main achievement of this paper is that it provides
a separation between locally decodable codes (LDCs)
and locally correctable codes (LCCs).
Indeed, this separation is obtained only for *linear*
codes and for *three*-query recovering algorithms,
but still is is a major achievement.

Specifically, for message length $k$ and block-length $n$,
the lower bound on 3-query LCCs
has the form $n=\exp(\Omega(k^{1/8}))$,
whereas the celebrated 3-query LDCs
satisfy $n=\exp(k^{o(1)})$
(i.e., $n=\exp(2^{\tildeO(\sqrt(\log k))})$.

When confining the discussion to *linear* codes,
the result is "somewhat tight" in two ways.
First (and most importantly),
such a (strong) separation is not possible
for 2-query recovering algorithms,
because in that case the known lower bound for LDCs is $n=\exp(\Omega(k))$,
whereas the Hadamard code is a 2-query LCC.
Second, an adequate RM-code is a 3-query LCC
with block-length $n=\exp(O(k^{1/2}))$.

#### The original abstract

We prove that the blocklength $n$ of a linear $3$-query locally correctable code (LCC) $\mathcal{L} \colon \mathbb{F}^k \to \mathbb{F}^n$ with distance $\delta$ must be at least $n \geq 2^{\Omega\left(\left(\frac{\delta^2 k}{(|\mathbb{F}|-1)^2}\right)^{1/8}\right)}$. 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 \geq \tilde{\Omega}(k^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 $n \leq 2^{O(k^{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 $q$-query LCCs and LDCs for any constant $q \geq 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].

See ECCC TR23-162.

Back to
list of Oded's choices.