Discrete Math Seminar: Nick Harvey

  • Date: 11/24/2015
  • Time: 16:00
Nick Harvey, UBC

University of British Columbia


Discrepancy theory and the Lovasz Local Lemma


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.

Other Information: 

Location: ESB 4127