Combinatorics and Probability Seminar
Vishesh Jain
UIC
Spencer's theorem in nearly input-sparsity time
Abstract: A celebrated theorem of Spencer states that for every set system $S_1,\dots,S_m \subseteq [n]$, there exists a coloring of the ground set with $\{\pm 1\}$ with discrepancy $O(\sqrt{n\log(m/n+2)})$. Algorithms for finding such colorings in polynomial time were designed nearly 25 years later, starting with a breakthrough work of Bansal. I will discuss recent work, joint with Ashwin Sah and Mehtaab Sawhney, in which we provide an algorithm for finding such a coloring in nearly input-sparsity time $\tilde{O}(n+\sum_{i=1}^{m}|S_i|)$.
Monday August 29, 2022 at 2:00 PM in 636 SEO