TOC Seminars Fall 2002

Wed, Sept. 18 Yuri Rabinovich, University of Haifa 
Low average distortion embeddings of finite metric spaces: properties and applications 
Tue, Sept. 24 Joint seminar with LIDS - Special location and time: 4pm-5pm, room 35-225
Greg Wornell, MIT Research Lab of Electronics 
Provably Secure Multimedia Content Authentication Systems 
Wed, Sept. 25 Vijay Vazirani, Georgia Institute of Technology 
How Intractable is the ``Invisible Hand'': Polynomial Time Algorithms for Market Equilibria 
Wed, Oct. 2 Avrim Blum, Carnegie Mellon University 
Correlation Clustering 
Wed, Oct. 9 Sanjeev Arora, Princeton University 
Proving Integrality Gaps without Knowing the Linear Program 
Wed, Oct. 16 Boaz Patt-Shamir, Tel Aviv University 
Perfectly Periodic Schedules 
Wed, Oct. 23 Grzegorz Malewicz, University of Connecticut 
Distributed Scheduling for Disconnected Cooperation 
Wed, Oct. 30 Michael Bender, SUNY Stony Brook 
Cache-Oblivious Data Structures 
Thu, Oct. 31 Joint seminar with LIDS - Special location and time: room 34-101
Manindra Agarwal, IIT Kanpur 
A polynomial time algorithm for primality testing 
Tue, Nov. 5 Joint seminar with LIDS - Special location and time: 4-5pm, room 35-225
Madhu Sudan, MIT LCS
List Decoding and Complexity Theory 
Wed, Nov. 6 Michael Langberg, Weizmann Institute 
Graphs with tiny vector chromatic numbers and huge chromatic numbers 
Wed, Nov. 27 Dorit Aharonov, MSRI 
Adiabatic Quantum State Generation and Statistical Zero Knowledge 
Wed, Dec. 4 Dimitrios Thilikos, Universitat Politecnica de Catalunya, Spain 
Retreat is Futile When You Want to Take Over the World 
Wed, Dec. 11 Subhash Khot, Princeton University 
Hardness of Coloring 3-Colorable 3-Uniform Hypergraphs