UW Combinatorics Talk

UW Combinatorics Seminar

Title: Two Needles in Exponential Haystacks (Colloquim Talk)

Joel Spencer

New York University

FRIDAY October 14**, 2:30pm
Room TBA

refreshments at 3:30pm

ABSTRACT 

Erd\H{o}s Magic, aka The Probabilistic Method, is a powerful tool for proving the existence of a combinatorial object, such as a coloring. A probability space is created for which the probability of success is positive. Hence the desired object must exist. But where is it? Here we examine instances in which the probability is exponentially small so that a randomized algorithm would not be in $P$. Nonetheless, we give two recent startling successes. Bansal: A quarter century ago this speaker showed that given $n$ sets on $n$ vertices there is a two-coloring so that all discrepencies are $O(\sqrt{n})$. He long conjectured that no polynomial time algorithm could find the coloring. Wrong! Nikhil Bansal, making ingenious use of semidefinite programming, finds the coloring and much more. Moser: Even longer ago, L\'aszl\'o Lov\'asz, with the Lov\'asz Local Lemma, showed (roughly!) that when bad events are mostly independent there is a positive probability that the random object has no bad events. Robin Moser gives a simple ``fix-it" randomized algorithm to find the object. The proof that the algorithm works, however, is most original. It gives a new and seemingly quite different proof of the Local Lemma itself. When the probabilistic method sieves an event with exponentially small probability the usual randomized algorithms will not find an actualization. We discuss two recent startling successes: Moser et.al. on the Lovasz Local Lemma and Bansal on the speaker's ``Six Standard Deviations Suffice."


Speaker's Contact Info: http://www.cs.nyu.edu/spencer/


Return to seminar home page

Sara Billey, Combinatorics Seminar, Mathematics Department, University of Washington,

Page loaded on September 21, 2011 at 10:43 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.