Abstract
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 * loglog 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, 2018]. That is, we show that if x -> (v_1 * x, v_2 * x, ... , v_n * x) is an arbitrary encoding map F_2^k -> F_2^n for the 3-query LCC, then all vectors in F_2^k can be written as a tilde{O}_{delta}(log n)-sparse linear combination of the v_i's, which immediately implies k <= tilde{O}_{delta}((log n)^2). The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least tilde{Omega}_{delta}(log n) of the v_i's. We achieve this using the recent breakthrough result of [Alon, Bucić, 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.