Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method

Avi Levy, Harishchandra Ramadas, Thomas Rothvoss

A well-known theorem of Spencer shows that any set system with $n$ sets over $n$ elements admits a coloring of discrepancy $O(\sqrt{n})$. While the original proof was non-construct…