A Stronger Bound for Linear 3-LCC

A q-locally correctable code (LCC) <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}$</tex> is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> queries to the word. The cases in which <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> is constant are of special interest, and so are the cases that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C$</tex> is linear. In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n=2^{\Omega(k^{1/8})}$</tex>. In this work we prove that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n=2^{\Omega(k^{1/4})}$</tex>. As Reed-Muller codes yield 3-LCC with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n=2^{O(k^{1/2})}$</tex>, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n=2^{\Omega(k^{1/3})}$</tex>.