| Title | : | Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles |
| Speaker | : | Venkatesan Guruswami (University of California, Berkeley) |
| Details | : | Wed, Jan 7, 2026 11:00 AM, @ Turing Hall (SSB 334) |
| Abstract | : | We show that any binary linear code of block length _n that is locally correctable with 3 queries against a constant fraction of adversarial errors must have dimension at most_$O(log^2 n log log n)$. This nearly matches the known construction of 3-query locally correctable codes (LCCs) based on quadratic Reed-Muller codes, which have dimension_$Theta(log^2 n)$. Our result significantly improves the best known upper bounds in the binary case: the $O(log^8 n)$ bound of Kothari and Manohar (STOC 2024), later improved to $O(log^4 n)$ by Yankovitz (FOCS 2024). Prior work bounded the dimension of 3-query LCCs by reducing them to 2-query locally decodable codes and invoking strong known bounds for the latter. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from (Iceland and Samorodnitsky, 2018). Specifically, we show that in any 3-query LCC with encoding map $x mapsto (v_1 cdot x, dots, v_n cdot x)$, every binary vector of length_k can be expressed as a $ ilde{O}(log n)$-sparse linear combination of the_$v_i$s. This then yields the desired dimension bound via a simple counting argument. The crux of our proof is a procedure that compresses any sufficiently large linear combination of the_$v_i$s into a sparser one, by exploiting the abundance of short linear dependencies amongst them. This step hinges on a recent result of Alon, Bucic, Sauermann, Zakharov, and Zamir (2023) on the existence of rainbow cycles in properly edge-colored graphs. We apply this theorem in a black-box manner to graphs that capture the combinatorial structure induced by the local correction constraints. Joint work with Omar Alrabiah. (Note: This talk is cross-listed as a CSE department seminar at IITM) |