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.

Intro
Discrepancy
Vector Balancing view
Spencer's Problem
Beck-Fiala Problem
This talk
A geometric view
Partial Coloring Lemma
Algorithmic Partial Coloring
Lovett Meka Algorithm
Beyond polytopes
Banaszczyk's Theorem
Algorithms for Banaszczyk
Loss in Partial Coloring
Algorithmic Banaszczyk (general)
Some Problems