Modern Erdos Magic

Series
Joint School of Mathematics and ACO Colloquium
Time
Thursday, November 2, 2017 - 11:05am for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Joel Spencer – Courant Institute, New York University – http://cs.nyu.edu/spencer/
Organizer
Lutz Warnke
Traditional Erdos Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain properties by showing that a random (appropriately defined) object will have those properties with positive probability. Modern Erdos Magic analyzes a random process, a random (CS take note!) algorithm. These, when successful, can find a "needle in an exponential haystack" in polynomial time. We'll look at two particular examples, both involving a family of n-element sets under suitable side conditions. The Lovasz Local Lemma finds a coloring with no set monochromatic. A result of this speaker finds a coloring with low discrepency. In both cases the original proofs were not implementable but Modern Erdos Magic finds the colorings in polynomial times. The methods are varied. Basic probability and combinatorics. Brownian Motion. Semigroups. Martingales. Recursions ... and Tetris!