Theory Reading Seminar: Schedule for Fall 2003

Date Presenter Presenting
Sep 4 nikhil Strategy Proof Mechanisms via Primal-dual Algorithms
Martin Pál, Éva Tardos
FOCS 2003
Sep 11 nikhil Simpler and Better Approximation Algorithms for Network Design.
Anupam Gupta, Amit Kumar and Tim Roughgarden
STOC 2003
Sep 18 amin Noam Nisan and Ilya Segal

XXXX 2003
Sep 25 vangelis Learning Juntas
Elchanan Mossel, Ryan O'Donnell, Rocco Servedio
STOC 2003
Oct 02 --- no meeting
Oct 16 tejas On the Implementation of Huge Random Objects
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
FOCS 2003
Oct 23 nisheeth Worst Case to Average Case Reductions for NP Problems
Andrej Bogdanov, Luca Trevisan
FOCS 2003
Nov 06 tejas On ε-biased generators in NC0
Elchanan Mossel, Amir Shpilka, Luca Trevisan
FOCS 2003
Nov 13 parik Deterministic Polynomial Time Primality Testing (Primes is in P)
Dec 04 viswa IP = PSPACE
Adi Shamir

For further details contact Tejas Iyer