| Feb 24 |
Kunal Talwar, U.C. Berkeley
Approximating Metrics by Simpler Metrics |
| Wed Feb 25 |
Harald Raecke, Carnegie Mellon University
Hierarchical Graph Decompositions for Oblivious Routing |
| Mar 9 |
Jon Feldman, Columbia University
Linear Programming (LP) Decoding Corrects a Constant Fraction of Errors |
| Mar 16 |
Tim Roughgarden, U.C. Berkeley and Stanford
Approximation via Cost Sharing (or, How to Build Good Networks by Flipping Coins) |
| Mar 30 |
Sean Hallgren, NEC Research
A Fast Quantum Algorithm for Computing the Unit Group of a Number Field |
| Apr 13 |
Eric Vigoda, University of Chicago and Toyota Technological Institute
Coupling Techniques and Random Sampling Colorings |
| Apr 27 |
Lisa Fleischer, Carnegie Mellon University and IBM T.J. Watson
Taxes for Heterogeneous, Selfish Users of a Multicommodity Network |
| May 4 |
Ravi Sundaram, Northeastern University
(Almost) Tight Bounds and Existence Theorems for Confluent Flows |
| May 11 |
Bradley Kuszmaul, MIT
Worst-Case Analysis of Randomized Exponential Backoff |
| POSTPONED |
Andrew C. Yao, Princeton University
Graph Entropy and Quantum Sorting Problems |
