We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a $3$-query locally correctable code (LCC) with dimension $\Theta(\log^2 n)$. Our result improves, for the binary field case, the $O_{\delta}(\log^8 n)$ bound obtained in the recent breakthrough of [Kothari and Manohar, 2023] (and the more recent improvement to $O_{\delta}(\log^4 n)$ for binary linear codes announced in [Yankovitz, 2024]).

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 [Iceland and Samorodnitsky, 2020]. That is, we show that if $x \mapsto (v_1 \cdot x, v_2 \cdot x, \ldots, v_n \cdot x)$ is an arbitrary encoding map $\mathbb{F}_2^k \to \mathbb{F}_2^n$ for the $3$-query LCC, then all vectors in $\mathbb{F}_2^k$ can be written as a $\widetilde{O}_{\delta}(\log n)$-sparse linear combination of the $v_i$'s, which immediately implies $k \le \widetilde{O}_{\delta}((\log n)^2)$. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least $\widetilde{\Omega}_{\delta}(\log n)$ of the $v_i$'s. We achieve this using the recent breakthrough result of [Alon, Bucic, Sauermann, Zakharov, and Zamir, 2023] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.

Added Theorem 1.3 on improved lower bounds for binary linear $r$-LCCs for odd $r \ge 5$ and accordingly changed Section 4. Removed conjecture relating rainbow and odd even covers.

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a $3$-query locally correctable code (LCC) with dimension $\Theta(\log^2 n)$. Our result improves, for the binary field case, the $O_{\delta}(\log^8 n)$ bound obtained in the recent breakthrough of [Kothari and Manohar, 2023] (and the more recent improvement to $O_{\delta}(\log^4 n)$ for binary linear codes announced in [Yankovitz, 2024]).

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 [Iceland and Samorodnitsky, 2020]. That is, we show that if $x \mapsto (v_1 \cdot x, v_2 \cdot x, \ldots, v_n \cdot x)$ is an arbitrary encoding map $\mathbb{F}_2^k \to \mathbb{F}_2^n$ for the $3$-query LCC, then all vectors in $\mathbb{F}_2^k$ can be written as a $\widetilde{O}_{\delta}(\log n)$-sparse linear combination of the $v_i$'s, which immediately implies $k \le \widetilde{O}_{\delta}((\log n)^2)$. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least $\widetilde{\Omega}_{\delta}(\log n)$ of the $v_i$'s. We achieve this using the recent breakthrough result of [Alon, Bucic, Sauermann, Zakharov, and Zamir, 2023] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.