Algorithmic Aspects of Discrepancy Theory
Explore the algorithmic aspects of discrepancy theory in this 45-minute lecture by Nikhil Bansal for the International Mathematical Union. Delve into key concepts such as vector balancing, Spencer's Problem, and the Beck-Fiala Problem. Gain insights into geometric perspectives, the Partial Coloring Lemma, and algorithmic approaches to partial coloring. Examine the Lovett Meka Algorithm and its applications beyond polytopes. Investigate Banaszczyk's Theorem and related algorithmic implementations. Analyze the loss in partial coloring and explore algorithmic Banaszczyk in general settings. Conclude with a discussion of some open problems in the field, providing a comprehensive overview of current research in discrepancy theory and its algorithmic implications.