Discrete Math Seminar: Nick Harvey

  • Date: 11/24/2015
  • Time: 16:00
Lecturer(s):
Nick Harvey, UBC
Location: 

University of British Columbia

Topic: 

Discrepancy theory and the Lovasz Local Lemma

Description: 

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