Rutgers Discrete Mathematics Seminar

Title: Two Needles in Exponential Haystacks

Speaker: Joel Spencer, Courant Institute

Date: Tuesday, October 25, 2011 2:00pm

Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ


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 on the Lovasz Local Lemma and Bansal on the speaker's ``Six Standard Deviations Suffice."