Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Omar Alrabiah, Venkatesan Guruswami · 2024
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$. 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}(\text{lo}\overline{\mathrm{g}}^{8}n)$bound obtained in the recent breakthrough of [1] (and the more recent improvement to$O_{\delta}(\log^{4}n)$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$x\rightarrow(v_{1}\cdot x,\ v_{2}\cdot x,\ \ldots,\ v_{n}\cdot x)$is an arbitrary encoding map$\mathbb{F}_{2}^{k}\rightarrow \mathbb{F}_{\underline{2}}^{n}$for the 3-query LCC, then all vectors in$\mathbb{F}_{2}^{k}$can be written as a$O_{\delta}(\log n)$-sparse linear com-bination of the$v_{i}{\prime}s$, which immediately implies$\overline{k}\leq\overline{O}_{\delta}((\log n)^{2})$. The proof of this fact proceeds by iteratively∼reducing the size of any arbitrary linear combination of at least$\Omega_{\delta}(\log n)$of the$v_{i}{\prime}s$. 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.