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