TOC Seminars Fall 2006

Sep 19

David ParkesHarvard University 
Adaptive and Truthful Online Mechanisms in Single-Valued Preference Domains

Sep 26 & 
Sep 28

Vijay VaziraniGeorgia 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 GoemansMassachusetts Institute of Technology
Minimum Bounded Degree Spanning Trees 
NOTE UNUSUAL LOCATION: 32-144

Oct 10

(columbus day)

Oct 17

Dan BonehStanford 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 TrevisanUniversity 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 ShmoysCornell University 
Approximation Algorithms for 2-Stage Stochastic Optimization Problems

Dec 12

TO BE RESCHEDULED