TOC Seminars Spring 2000

January 6, 2000
Alexander A. Razborov, Princeton University and Steklov Mathematical Institute
Space Complexity in Propositional Calculus
Host: Silvio Micali

February 10, 2000 (Thursday)
Rafail Ostrovsky, Telcordia Technologies
Near-Optimal Local Control Universal Packet-Routing Algorithms
Host: Silvio Micali

February 29, 2000
Allan Borodin, University of Toronto
On the Competitive Theory and Practice of Portfolio Selection
Host: Madhu Sudan

March 2, 2000 (Thursday)
Luca Trevisan, Columbia University
Randomness Extractors and Pseudorandom Generators
Hosts: Silvio Micali and Madhu Sudan

March 7, 2000
Leslie Valiant, Harvard University
Robust Logics
Host: Madhu Sudan

March 14, 2000
Idit Keidar, MIT
A scalable group membership algorithm
Host: Nancy Lynch

March 28, 2000
Peter Winkler, Bell Labs, Lucent Technologies
On Playing Golf With Two Balls
Host: Madhu Sudan

March 31, 2000 (Friday: TOC/CIS Seminar)
Simson Garfinkel,
Database Nation -- Why Cryptography is Not Enough
Host: Ron Rivest

April 4, 2000
Costas Busch, Brown University
Greedy Hot-Potato Routing
Host: Nancy Lynch

April 7, 2000 (Friday: Joint TOC/CIS Seminar, in Room NE43-308)
Adi Shamir, Weizmann Institute
Real Time Cryptanalysis of A5/1 on a PC
Host: Ron Rivest

April 11, 2000
Salil Vadhan, MIT
A New Graph Product and Simple Constructions of Constant-Degree Expanders and Extractors
Host: Madhu Sudan

April 18, 2000
Judy Goldsmith, Univ. of Kentucky
The Complexity of Model Minimization
Host: Madhu Sudan