DIMACS/CS Light Seminar: Theoretical Computer Science

Place:                   Core 431.
Time:                   Tuesdays 2.00 -- 3.00 PM
Contact:             Eric Allender and S. Muthukrishnan .
Index number:       49837 (01) 

See MATH seminar series and the home page for Fall 04 Spring 04 and Fall 2003 Theory seminars.

NOTE to external speakers: Please see dimacs webpage for directions. Please arrive a little before 2 PM at Muthu's or Eric's offices.
DATE   SPEAKER TITLE (link to abstracts) Notes
Jan 25

Feb 1 Asaf Shapira Every Monotone Graph Property is Testable Core 433
Feb 8 Rocco A. Servedio Learning decision trees and DNF formulas in the average case
Feb 15 Gopal Pandurangan  Nearest Neighbor Trees and their Algorithmic Applications
Feb 22 Moses Charikar Aggregating inconsistent information: Ranking and Clustering
Mar 1 Martin Pal Stochastic Steiner tree without the root Core 433; Muthu away
Mar 8 Yury Makarychev  O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems Core 433
Mar 22 Konstantin Makarychev  Quadratic forms on graphs Core 229 
Mar 29 Guy Kindler New explicit constructions of randomness extractors from weak
sources, and of bipartite Ramsey graphs.

Apr 05 Mike Saks
Every boolean decision tree has an influential variable

Apr 12 Mario Szegedy Near optimality of the priority sampling procedure

Apr 19 M. Alekhnovitch
Hardness of Approximating the Closest Vector Problem with Pre-Processing

Apr 26 Sanjeev Khanna New Algorithms and Hardness Results for Disjoint Paths Problem

May 3 Sudipto Guha
Have epsilons helped you lately? Algorithmic impact on
Histogram & Wavelet construction problems

May 26
Seth Pettie
Approximating Shortest Paths with Purely Additive Spanners Host: Farach-Colton