TOC Seminars Spring 2006

Feb 14

Piotr IndykMassachusetts 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 GallagerMassachusetts Institute of Technology
The Impact of Information Theory on Information Technology

Mar 7

ROOM CHANGE: 4-237, Michael KrivelevichTel Aviv University
Property Testing in Graphs of General Density

Mar 14

Avrim BlumCarnegie Mellon University
On Decision-Making Without Regret, Routing Games, and Convergence to Equilibria

Mar 21

Leslie ValiantHarvard University
A Quantitative Theory of Neural Computation

Mar 28

(spring break)

Apr 4

Moses CharikarPrinceton University 
Near-Optimal Algorithms for Unique Games

Apr 11

Venkat GuruswamiUniversity of Washington 
Capacity-Achieving List Decodable Codes for Worst-Case Errors

Apr 18 (patriot's day)
Apr 25

Joint TOC-LIDS Colloquium 
Leonard SchulmanCalifornia Institute of Technology
Error-Correcting Codes for Automatic Control

May 2

ROOM CHANGE: 6-120, Erik DemaineMassachusetts Institute of Technology
Linkage Folding: From Steam Engines to Proteins

May 8

Note Unusual Monday Date 
ROOM CHANGE: 32-G575 (Theory Lab), Tali KaufmanMassachusetts Institute of Technology 
Property Testing of Codes - Results, Methods and Limitations

May 16

Subhash KhotGeorgia Institute of Technology 
Lower Bounds for Approximating MAX-CUT and Sparsest Cut