Discrepancy Minimization via Regularization

At the recent workshop on Optimization and Algorithm Design, Adrian Vladu (IRIF) introduced a new algorithmic framework for discrepancy minimization based on regularization. In this joint work with Lucas Pesenti, Vladu demonstrates how varying the regularizer makes it possible to reinterpret several breakthrough works in algorithmic discrepancy, ranging from Spencer’s theorem to Banaszczyk’s bound. Using these techniques, the researchers also show that the Beck-Fiala and Komlós conjectures are true for a new regime of pseudorandom instances.