Modern Erdoes Magic

Joint School of Mathematics and ACO Colloquium
Thursday, November 2, 2017 - 11:05
1 hour (actually 50 minutes)
Skiles 006
Courant Institute, New York University
Traditional Erdoes Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain propertiesby showing that a random (appropriately defined) object will have those properties with positive probability.  Modern Erdoes 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 Erdoes Magic finds the colorings in polynomial times. The methods are varied.  Basic probability and combinatorics. Brownian Motion.  Semigroups.  Martingales. Recursions  ... and Tetris!