Discrepancy Minimization via Regularization

Explore a groundbreaking algorithmic framework for discrepancy minimization based on regularization in this 57-minute lecture by Adrian Vladu from IRIF. Discover how varying the regularizer provides new interpretations of landmark works in algorithmic discrepancy, from Spencer's theorem to Banaszczyk's bound. Learn about the application of these techniques to prove the Beck-Fiala and Komlos conjectures for a novel regime of pseudorandom instances. Delve into the joint work with Lucas Pesenti, presented at SODA 2023, as part of the Optimization and Algorithm Design series at the Simons Institute.

Discrepancy Minimization via Regularization