THEORY SEMINAR: Please join us on Sep 8th at 10am in Siebel 3401 where Haotian Jiang will give a talk: "Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk".
Please see the abstract below:
Abstract: The Beck-Fiala Conjecture asserts that any set system of n elements with degree k has combinatorial discrepancy O(\sqrt{k}). A substantial generalization is the Koml\'os Conjecture, which states that any m by n matrix with columns of unit Euclidean length has discrepancy O(1).
In this talk, we describe an O(log^{1/4} n) bound for the Koml\'os problem, improving upon the O(log^{1/2} n) bound due to Banaszczyk from 1998. We will also see how these ideas can be used to resolve the Beck-Fiala Conjecture for k \gg \log^2 n, and give a \tilde{O}(k^{1/2} + \log^{1/2} n) bound for smaller k, which improves upon Banaszczyk's O(k^{1/2} \log^{1/2} n) bound. These results are based on a new technique of "Decoupling via Affine Spectral Independence" in designing rounding algorithms, which might also be useful in other contexts.
This talk is based on joint work with Nikhil Bansal (University of Michigan).
Bio: Haotian Jiang is an assistant professor in the Computer Science Department at the University of Chicago. Previously, he obtained his PhD from the University of Washington under the supervision of Yin Tat Lee, and then he was a Postdoctoral Researcher at Microsoft Research Redmond. His research focuses on algorithms and optimization. He has received various recognitions for his work, including a best student paper award at SODA 2021 and a best paper award at SODA 2025.: