TOC Seminar Spring 2002

Wednesday February 6th
Peter Clote, Boston College
Mitochondrial Eve and Population Bottlenecks    

Tuesday, February 12th, 4:15pm in Room NE43-941 (Note the unusual day, time and room.)
Shmuel Safra, Tel Aviv University
The Importance of Being Biased    

Wednesday February 13th
Avner Magen, NEC Research Institute
Reduction of dimensionality in Euclidean Space that Preserve Volumes, and Applications

Monday February 25th, 4:15pm in NE43-518 (Note day and time.)
Omer Reingold, AT&T and IAS
The Zigzag Graph Product and Constant-Degree Lossless Expanders

Wednesday February 27th
Tugkan Batu, University of Pennsylvania
Testing Properties of Distributions

Wednesday March 6th
John Gilbert, Xerox PARC
Support-Graph Preconditioning

Wednesday March 13th
Andreas Schulz, MIT
Combinatorial Auctions

Wednesday March 20th
Ravi Kannan, Yale University
Random Induced Subproblems

Wednesday April 3rd
Tal Malkin, AT&T
Secure Multiparty Computation of Approximations

Wednesday April 10th
Cynthia Dwork, Microsoft
Zero-Knowledge and Proof Auditors

Wednesday April 17th
Martin Strauss, AT&T
Near-Optimal Sparse Fourier Representations via Sampling

Wednesday May 1st
Salil Vadhan, Harvard University
Randomness Conductors and Constant-Degree Lossless Expanders

Wednesday May 8th
Ike Chuang, MIT
Quantum Digital Signatures

Tuesday May 14th, 4:15pm in NE43-941 (Note room, day and time.)
Amir Shpilka, Weizmann Institute
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

Wednesday May 15th
Christos Papadimitriou, Berkeley
Algorithmic Aspects of the Internet

Wednesday May 29th
Ronitt Rubinfeld, NEC Research Institute
What can we do in sublinear time?

Wednesday June 5th
Ran Raz, Weizmann Institute
Resolution Lower Bounds for the Weak Pigeonhole Principle