TCS+ talk: Wednesday, November 19, Haotian Jiang, U Chicago
Clement Canonne
Our next talk will take place this coming Wednesday, November 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Haotian Jiang from U Chicago will speak about "Beck-Fiala and Komlós Bounds Beyond Banaszczyk" (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Haotian Jiang (U Chicago)
Title: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
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ós 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 \tilde{O}(log^{1/4} n) bound for the Komlós 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 \geq \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).