| Title | : | Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles |
| Speaker | : | Prof. Venkatesan Guruswami (University of California, Berkeley) |
| Details | : | Wed, 7 Jan, 2026 11:00 AM @ SSB 334 |
| Abstract: | : | 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 -> (v1 * x, ..., vn * x), every binary vector of length k can be expressed as an O~(log n)-sparse linear combination of the vi'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 vi'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. ========================================= Speaker Bio: Prof. Venkatesan Guruswami is the Chancellor's Professor at the Dept of EECS, Professor at the Dept of Mathematics, and the Director of the Simons Institute for the Theory of Computing at UC Berkeley. Dr Guruswami's research interests span several topics in theoretical computer science, including the theory of error-correcting codes, the approximability of fundamental optimisation problems, explicit combinatorial constructions, pseudorandomness, probabilistically checkable proofs, computational complexity theory, and algebraic algorithms. Dr. Guruswami currently serves as the Editor-in-Chief for the Journal of the ACM and has in the past served as the Editor-in-Chief for the ACM Transactions on Computation Theory. Dr. Guruswami is a recipient of the Presburger Award (2012), Packard Fellowship (2005), Sloan Fellowship (2005), NSF CAREER Award (2004), the ACM Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000). ========================================= |
