| Feb 14 |
Piotr Indyk, Massachusetts Institute of Technology
Near-Optimal Hashing Algorithm for the Approximate Nearest Neighbor Problem |
| Feb 21 |
Nir Shavit, Sun Microsystems Laboratories
Virtual Leashing: Internet-Based Software Piracy Protection |
| Feb 28 |
Robert Gallager, Massachusetts Institute of Technology
The Impact of Information Theory on Information Technology |
| Mar 7 |
ROOM CHANGE: 4-237, Michael Krivelevich, Tel Aviv University
Property Testing in Graphs of General Density |
| Mar 14 |
Avrim Blum, Carnegie Mellon University
On Decision-Making Without Regret, Routing Games, and Convergence to Equilibria |
| Mar 21 |
Leslie Valiant, Harvard University
A Quantitative Theory of Neural Computation |
| Mar 28 |
(spring break) |
| Apr 4 |
Moses Charikar, Princeton University
Near-Optimal Algorithms for Unique Games |
| Apr 11 |
Venkat Guruswami, University of Washington
Capacity-Achieving List Decodable Codes for Worst-Case Errors |
| Apr 18 |
(patriot's day) |
| Apr 25 |
Joint TOC-LIDS Colloquium
Leonard Schulman, California Institute of Technology
Error-Correcting Codes for Automatic Control |
| May 2 |
ROOM CHANGE: 6-120, Erik Demaine, Massachusetts Institute of Technology
Linkage Folding: From Steam Engines to Proteins |
| May 8 |
Note Unusual Monday Date
ROOM CHANGE: 32-G575 (Theory Lab), Tali Kaufman, Massachusetts Institute of Technology
Property Testing of Codes - Results, Methods and Limitations |
| May 16 |
Subhash Khot, Georgia Institute of Technology
Lower Bounds for Approximating MAX-CUT and Sparsest Cut |