TOC Seminars Fall 2006 | MIT CSAIL Theory of Computation

Sep 19	David Parkes, Harvard University Adaptive and Truthful Online Mechanisms in Single-Valued Preference Domains
Sep 26 & Sep 28	Vijay Vazirani, Georgia Institute of Technology New Market Models and Algorithms This is a two-part series, joint with the ORC seminar. Sep 26 TALK LOCATION: 32-G449 (usual location) Sep 28 TALK LOCATION: E40-298
Oct 3	Michel Goemans, Massachusetts Institute of Technology Minimum Bounded Degree Spanning Trees NOTE UNUSUAL LOCATION: 32-144
Oct 10	(columbus day)
Oct 17	Dan Boneh, Stanford University Queries on Encrypted Data
Thu Oct 26	Irit Dinur, Hebrew University Probabilistically Checkable Proofs and Gap Amplification NOTE UNUSUAL DAY AND LOCATION: 56-114
Oct 31	Luca Trevisan, University of California at Berkeley Gowers Uniformity, Influence of Variables and Probabilistically Checkable Proofs
Nov 7	Richard Karp, University of California at Berkeley Balanced Network Decompositions for Internet Routing
Nov 14	Uriel Feige , Microsoft Research and Weizmann Institute Algorithms for Deciding Satisfiability of Random Formulas
Nov 21	(thanksgiving week)
Nov 28	James Aspnes, Yale University Population Protocols
Dec 5	David Shmoys, Cornell University Approximation Algorithms for 2-Stage Stochastic Optimization Problems
Dec 12	TO BE RESCHEDULED