Spencer's theorem in nearly input-sparsity time

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

A celebrated theorem of Spencer states that for every set system $S_1,\dots ,S_m\subseteq [n]$, there is a coloring of the ground set with $\{\pm 1\}$ with discrepancy $O(\sqrt{n\…