TOC Seminar Spring 2009

Feb 3 Robert Kleinberg, Cornell University
A Learning-Theoretic Refinement of the Price of Anarchy
Host: Silvio Micali
Feb 10 Salil Vadhan, Harvard University
Inaccessible Entropy
Host: Scott Aaronson
Feb 17 Andrew Goldberg, Microsoft Research -- Silicon Valley
Reach for A*: an Efficient Point-to-Point Shortest Path Algorithm
Host: Charles Leiserson
Feb 24 Joint TOC-LIDS Seminar
Sergiu Hart, The Hebrew University
Dynamics and Equilibrium
Host: Silvio Micali
Feb 25
Unusual Time: WED
Unusual Place: 32-124
Alexander Razborov, University of Chicago
A simple proof of Bazzi's theorem
Host: Scott Aaronson
Mar 3 Constantinos Daskalakis, Microsoft Research New England
Symmetries and the Complexity of Nash Equilibria
Host: Scott Aaronson
Mar 10 Ketan Mulmuley, University of Chicago
On P vs NP, Geometric Complexity Theory, and the Riemann Hypothesis
Host: Scott Aaronson
Mar 17 Mark Braverman, Microsoft Research New England
Poly-logarithmic Independence Fools AC0 Circuits
Host: Scott Aaronson
Mar 24 Spring Vacation: no talk
Apr 7 Venkatesan Guruswami, University of Washington
List decoding product and interleaved codes
Host: Piotr Indyk
Apr 14 Shivani Agarwal, MIT
Ranking Problems in Machine Learning: Theory and Applications
Host: Scott Aaronson
Apr 21 Patriot's Day: no talk
Apr 28 Anna Gilbert, University of Michigan
A Survey of Sparse Approximation
Host: Piotr Indyk
May 5
Unusual time: 11AM
Unusual place: Star (32-D463)
Ryan O'Donnell, Carnegie Mellon University
KKL, Kruskal-Katona, and monotone nets
Host: Scott Aaronson
May 12 Yuval Ishai, Technion and UCLA
Extracting Correlations
Host: Scott Aaronson
May 19 Joint TOC-LIDS Seminar
Silvio Micali, MIT
A New Approach to Auctions and Mechanism Design
Host: Scott Aaronson