TOC Seminars Spring 2004

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