
Sept 10, 2009  Sudipto Guha
Decouple and Balance: Approximation algorithms for hard bandit problems

Sept 17, 2009  Anup Rao
Direct Sums in Randomized Communication Complexity

Sept 24, 2009  Yuval Rabani
Monotonicity in bargaining networks

Oct 1, 2009  Gil Kalai
Analysis and Probability of Boolean functions: results and Problems

Oct 8, 2009  Guy Rothblum
PrivacyPreserving Data Release: Efficient Algorithms and Hardness Results

Oct 15, 2009  Mihai Patrascu
Hardness of Nearest Neighbor under Linfinity

Oct 22, 2009 (Note: Room 317)  Charles Fefferman
Interpolation of Functions

Oct 29, 2009  Ofer Neiman
Nearly Tight Low Stretch Spanning Trees

Nov 5, 2009  Ariel Gabizon
Simple Affine Extractors using Dimension Expansion

Nov 12, 2009  Boaz Barak
Computational Complexity and Information Asymmetry in
Financial Products

Nov 19, 2009  Alex Andoni
Query Complexity of Edit Distance

Nov 26, 2009  Thanksgiving, no seminar

Dec 3, 2009  Seminar cancelled

Dec 10, 2009  Ramamohan Paturi
On the Complexity of Circuit Satisfiability


 Location: Warren
Weaver Hall (251 Mercer Street), Room 1314
 Time: Thursdays 2:15pm
 To subscribe to mailing list: write to khot cs nyu edu

