January 24th, 2008 - Chee Yap
Integral Analysis of Adaptive Algorithms: Real Root Isolation

January 31st, 2008 - Venkatesan Guruswami
Expander codes, compressed sensing matrices, and Euclidean sections of L_1

February 7th, 2008 - Alexander Razborov
(non-standard time/place) 11:30-12:30am, Room 102
The Sign-Rank of $AC0$

February 14th, 2008 - Rocco Servedio
Learning, Testing and Approximating Halfspaces

February 21st, 2008 - Prasad Raghavendra
Optimal Algorithms and Inapproximability Results for every CSP?

February 28th, 2008 - Nikhil Bansal
Degree bounded network design

March 6th, 2008 - Noga Alon
Expanders, Disjoint Paths and Universal Graphs

March 13th, 2008 - Troy Lee
Disjointness is hard in the multi-party number-on-the-forehead model

March 20th, 2008 - Rishi Saket
On Hardness of Learning Intersection of Two Halfspaces.

March 27th, 2008 - Jordan Kerenidis
Interactive and Noninteractive Zero Knowledge are equivalent in the Help Model

April 3rd, 2008 - Richard Cole
Fast-Converging Tatonnement Algorithms for One-Time and Ongoing Market Problems

April 10th, 2008 - Parikshit Gopalan
Agnostically Learning Decision Trees.

April 17th, 2008 - Cancelled

April 24th, 2008 - Navin Goyal
The VPN conjecture is true

May 1st, 2008 - Adi Gottlieb
Optimal Dynamic Spanners

May 8th, 2008 - Vijay Vazirani
Nash Bargaining via Flexible Budget Markets

Details

• Location: Warren Weaver Hall (251 Mercer Street), Room 1314
• Time: Thursdays 2:15pm