- Date: –16:00
- Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 80101
- Lecturer: Joel Spencer
- Contact person: Thomas Kragh
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!