============================================================
   Seminário de Teoria da Computaçăo e Combinatória (TCC)

============================================================

Título:      Two Needles in Exponential Haystacks
            
Palestrante: Joel Spencer
             Courant Institute
             New York University

Hora e Data: 14h, sexta-feira, 11 de novembro de 2011

Local:       auditório do NUMEC

Resumo:

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 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á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.