Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

We prove that a binary linear code of block length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> that is locally correctable with 3 queries against a fraction <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta &gt; 0$</tex> of adversarial errors must have dimension at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o_{\delta} ( &gt;\log^{2}n$</tex>. log log <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> ). This is almost tight in view of quadratic Reed-Muller codes being a 3-query locally correctable code (LCC) with dimension <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta^{-}(\log^{2}n)$</tex>. Our result improves, for the binary field case, the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{\delta}(\text{lo}\overline{\mathrm{g}}^{8}n)$</tex> bound obtained in the recent breakthrough of [1] (and the more recent improvement to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{\delta}(\log^{4}n)$</tex> for binary linear codes announced in [2]). Previous bounds for 3-query linear LCCs proceed by constructing a 2-query locally decodable code (LDC) from the 3-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [3]. That is, we show that if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x\rightarrow(v_{1}\cdot x,\ v_{2}\cdot x,\ \ldots,\ v_{n}\cdot x)$</tex> is an arbitrary encoding map <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{2}^{k}\rightarrow \mathbb{F}_{\underline{2}}^{n}$</tex> for the 3-query LCC, then all vectors in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{2}^{k}$</tex> can be written as a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{\delta}(\log n)$</tex> -sparse linear com-bination of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$v_{i}{\prime}s$</tex>, which immediately implies <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\overline{k}\leq\overline{O}_{\delta}((\log n)^{2})$</tex>. The proof of this fact proceeds by iteratively<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∼</inf> reducing the size of any arbitrary linear combination of at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega_{\delta}(\log n)$</tex> of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$v_{i}{\prime}s$</tex>. We achieve this using the recent breakthrough result of [4] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.