Geometry and Topology Seminar

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 \tilde{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 \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.