TOC Seminar Spring 2001

February 28, 2001
NE43-941
Rocco Servedio, Harvard University
Title: Learning DNF in Time 2^{n^{1/3}}

March 14, 2001
NE43-941
Peter Winkler, Lucent Technologies
Title: Games People Don't Play

April 4, 2001
NE43-941
Dan Spielman, MIT
Title: Smoothed Analysis of Algorithms: Why The Simplex Algorithm Usually Takes Polynomial Time

April 11, 2001
NE43-518
Lance Fortnow, NEC Research Institute
Title: Comparing Notions of Full Derandomization

April 25, 2001
NE43-518
David Clark, MIT
Title: Networking: What does theory have to do with it?

May 2, 2001
NE43-518
Avi Wigderson, Hebrew University and IAS
Title: Semi-direct product in groups and Zig-zag product in graphs: Connections and applications

May 9, 2001
NE43-518
Michael Mitzenmacher, Harvard University
Title: Compressed Bloom Filters and Compressing the Web Graph

May 15, 2001 at 4 p.m.
NE43-941
Anna Karlin, University of Washington
Title: Web Search Via Hub Synthesis

May 23, 2001 at 4 p.m.
NE43-518
Leonid Levin, Boston University
Title: On One-way Functions, and Everything Else