• Date: –16:00
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 80101
  • Lecturer: Joel Spencer
  • Contact person: Thomas Kragh
  • Seminarium

Needles in Exponential Haystacks

Abstract: For Paul Erdos, the goal was to prove the existence of a mathematical
object.  In this century we further search for an efficient algorithm to find the
object.  We discuss the celebrated Local Lemma of Lovasz and this speaker's "Six Standard Deviation" discrepency result.  Their original proofs were existential.
Modern arguments (including one by Donald Knuth using Tetris!) give efficient 
algorithms -- and new proofs!