| 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 |
