# UW-PIMS Mathematics Colloquium: Joel Spencer (Courant/NYU)

## Topic

Two needles in exponential haystacks

## Speakers

## Details

ErdÃ¶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 givenn sets
on n vertices there is a two-coloring so that all discrepancies are
O(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Ã¡szlÃ³ LovÃ¡sz, with the LovÃ¡sz 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 LovÃ¡sz Local Lemma and Bansal on the speaker's "Six Standard Deviations Suffice."

Bansal: A quarter century ago this speaker showed that given

Moser: Even longer ago, LÃ¡szlÃ³ LovÃ¡sz, with the LovÃ¡sz 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 LovÃ¡sz Local Lemma and Bansal on the speaker's "Six Standard Deviations Suffice."

## Additional Information

Location: Mechanical Engineering Building, Room 238

For more information please visit University of Washington Department of Mathematics

Joel Spencer

This is a Past Event

Event Type

**Scientific, Seminar**

Date

**October 14, 2011**

Time

**-**

Location

University of Washington