Starting next week, our seminar will host a mini-course on Discrepancy Theory ministered by Gleb Smirnov. The details of the first lecture are below.

Abstract: Discrepancy theory is the study of how evenly we can distribute or color elements in combinatorial structures to minimize maximum deviations. In this mini-course, we will consider core classical results of the theory, such as Steinitz's rearrangement theorem, Banaszczyk's sign discrepancy theorems, and the Beck-Fiala conjecture. All these results are elementary to state. For instance, Steinitz's theorem answers how to rearrange a finite sequence of unit vectors with zero sum in such a way that all partial sums remain small. We will discuss simple proofs of some (slightly weakened) versions of these theorems, which only require a modest amount of elementary probability and combinatorics. Along the way, we will also consider applications of discrepancy results to rounding problems in semidefinite programming and approximation algorithms.