Talks are on Tuesdays at 4:15pm, with refreshments at 4:00pm.

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