Sept 4, 2008 - Vahab Mirrokni
Submodular Optimization: Maximization, Learning, and Applications

Sept 11, 2008 - Yevgeniy Dodis
On Extractors, Error-Correction and Hiding All Partial Information

Sept 18, 2008 - Howard Karloff
On Selecting Nodes for Monitoring A Network

Sept 25, 2008 - Zeev Dvir
The finite field Kakeya conjecture and applications to the construction of mergers and extractors

Oct 2, 2008 - Dana Moshkovitz
Two Query PCP with Sub-Constant Error

Oct 2, 2008 - Nikhil Srivastava
Twice-Ramanujan Sparsifiers

Oct 16, 2008 - Per Austrin
Randomly Supported Independence

Oct 23, 2008 - We have two seminars.

David Kempe (At 2:15pm in Room 1314)
On the Bias of Traceroute Sampling

Asaf Nussbaum (At 4:00pm in Room 317)
Pseudorandom and k-wise independent random graphs

Oct 30, 2008 - No seminar; FOCS + Princeton Geometry Workshop

Nov 6, 2008 - Alex Andoni
Overcoming the L_1 non-embeddability barrier: Algorithms for product spaces

Nov 13, 2008 - Mike Saks
Distributed Monotonicity Reconstruction

Nov 20, 2008 - Rohit Khandekar
Stateless Distributed Gradient Descent for Positive Linear Programs

Nov 27, 2008 - No seminar; Thanksgiving

Dec 1-5, 2008 - No theory seminar, instead:

Dec 1: Avi Wigderson (Math colloquium at 3:45pm in Room 1302)
Expander graphs: a playground for combinatorics, algebra and computer science

Dec 5: Room 109
IBM-NYU-Columbia Theory Day

Details

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