Abstract
We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthrough works in algorithmic discrepancy, ranging from Spencer's theorem to Banaszczyk's bound. Using our techniques, we also show that the Beck-Fiala and Komlos conjectures are true for a new regime of pseudorandom instances.
Joint work with Lucas Pesenti (SODA 2023).