Talks are on Tuesdays at 4:15pm, with refreshments at 4:00pm in Room 32-G449 (Kiva).

Sept 21:	Mikkel Thorup, AT&T Labs-Research Sampling to Estimate Arbitrary Subset Sums
Thursday Sept 23:	Room 32-D463 (Star), 4:15 PM Andrew Goldberg, Microsoft Research Computing Shortest Paths: A* Search Meets Triangle Inequality
Sept 28:	Mike Mahoney, Yale University Fast Monte Carlo Algorithms for Massive Data Sets and Approximating Max-Cut
Oct 5:	Iordanis Kerenidis, Massachusetts Institute of Technology Quantum Encodings and Applications to Communication Complexity and Locally Decodable Codes
Friday Oct 8:	Room 32-G575 at 10:30 AM Danielle Micciancio, University of California San Diego Worst-Case to Average-Case Reductions Based on Gaussian Measures
Oct 12:	Eli Ben-Sasson, Harvard University Short and Simple PCPs with Poly-Log Rate and Query Complexity
Oct 19:	Julia Chuzhoy, Massachusetts Institute of Technology The Hardness of Metric Labeling
Nov 2:	Erik D. Demaine, Massachusetts Institute of Technology Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth
Nov 9:	Cynthia Dwork, Microsoft Toward Privacy in Public Databases
Nov 12:	Guy Kortsarz, Rutgers University Approximating Directed Multicut and Related Problems
Nov 30:	Alex Russell, University of Connecticut Nonabelian PCPs and the Complexity of Solving Equations over Finite Groups
Dec 7:	Dimitris Achlioptas, Microsoft A new Look at the Second Moment Method
Dec 8:	Robert Krauthgamer, IBM A Metric Notion of Dimension and its Algorithmic Applications