Discrete Math Seminar: Nick Harvey

Discrepancy theory has been an important research area in combinatorics and geometry for several decades. Recently there has been a lot of activity in discrepancy theory, in two directions. The first is efficient algorithmic proofs for classical discrepancy results that previously had only non-constructive proofs. The second is matrix generalizations of some classical discrepancy results, the canonical example of which is the solution of the Kadison-Singer conjecture by Marcus-Spielman-Srivastava (Polya Prize 2014).

In this talk I will give an overview of the field of discrepancy theory, then discuss a self-contained result of my own that uses the Lovasz Local Lemma to solve a discrepancy question that was overlooked for many years.

I will give a second talk on the Lovasz Local Lemma, focusing on algorithms, on Wednesday November 25th in the Probability Seminar.