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

We prove that a binary linear code of block length n that is locally correctable with 3 queries against a fraction δ > 0 of adversarial errors must have dimension at most O_δ(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 Θ(log^2 n). Our result improves, for the binary field case, the O_δ(log^8 n) bound obtained in the recent breakthrough of (Kothari and Manohar, 2023) (arXiv:2311.00558) (and the more recent improvement to O_δ(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) (arXiv:1802.01184). That is, we show that if x ↦ (v_1 · x, v_2 · x, …, v_n · x) is an arbitrary encoding map 𝔽_2^k →𝔽_2^n for the 3-query LCC, then all vectors in 𝔽_2^k can be written as a O_δ(log n)-sparse linear combination of the v_i's, which immediately implies k ≤O_δ((log n)^2). The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least Ω_δ(log n) of the v_i's. We achieve this using the recent breakthrough result of (Alon, Bucić, Sauermann, Zakharov, and Zamir, 2023) (arXiv:2309.04460) on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.