TOC Seminars Fall 2004

Sept 21: Mikkel ThorupAT&T Labs-Research
Sampling to Estimate Arbitrary Subset Sums
Thursday Sept 23: Room 32-D463 (Star), 4:15 PM
Andrew GoldbergMicrosoft Research
Computing Shortest Paths: A* Search Meets Triangle Inequality
Sept 28: Mike MahoneyYale University
Fast Monte Carlo Algorithms for Massive Data Sets and Approximating Max-Cut
Oct 5: Iordanis KerenidisMassachusetts Institute of Technology
Quantum Encodings and Applications to Communication Complexity and Locally Decodable Codes
Oct 8:
Room 32-G575 at 10:30 AM
Danielle MicciancioUniversity of California San Diego
Worst-Case to Average-Case Reductions Based on Gaussian Measures
Oct 12: Eli Ben-SassonHarvard 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. DemaineMassachusetts Institute of Technology
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth
Nov 9: Cynthia DworkMicrosoft
Toward Privacy in Public Databases
Nov 12: Guy KortsarzRutgers University
Approximating Directed Multicut and Related Problems
Nov 30: Alex RussellUniversity of Connecticut
Nonabelian PCPs and the Complexity of Solving Equations over Finite Groups
Dec 7: Dimitris AchlioptasMicrosoft
A new Look at the Second Moment Method
Dec 8: Robert KrauthgamerIBM
A Metric Notion of Dimension and its Algorithmic Applications