Discrepancy Minimization via Regularization
Provides a new theoretical framework that simplifies and extends known results in discrepancy theory, with implications for combinatorial optimization and algorithm design.
The paper introduces a regularization-based framework for discrepancy minimization that unifies several prior results and proves the Beck-Fiala and Komlós conjectures hold for pseudorandom instances.
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 [Spencer 1985, Bansal 2010] to Banaszczyk's bounds [Banaszczyk 1998, Bansal-Dadush-Garg 2016]. Using our techniques, we also show that the Beck-Fiala and Komlos conjectures are true in a new regime of pseudorandom instances.