DIMACS/CS Light Seminar: Theoretical Computer Science

Place:                   Core 431.
Time:                   Mondays 3.30 -- 4.30 PM
Contact:               Eric Allender and S. Muthukrishnan.
Index number:     
198:500  ( 11352 )

See MATH seminar series and the home page for Spring 04 and Fall 2003 Theory seminars.
NOTE to external speakers: Please see dimacs webpage for directions.

TITLE (link to abstracts)
Sept 6

 Labor Day.
Sept 13
Robert  Spalek
Quantum and Classical Strong Direct Product Theorems and Optimal  Time-Space Tradeoffs

Sept 20
Howard Karloff,
AT&T Research
How Well Can the *Directed* Traveling Salesman Problem Be Approximated?
Core 433.
Eric away
Sept 27
Scott Aaronson
Formula Size Lower Bounds and Quantum States
Core 433.
 M. Goldberg
Oct 4
Oded Lachish
Univ of Haifa
Testing Periodicity

Oct 11
S. Muthukrishnan, Rutgers U. Nonuniform sparse approximation using Haar Wavelets  Eric away.

Oct 18
Eric Allender
Rutgers Univ
Topology and Small Circuit Complexity Classes Core 433.
Oct 25
David Johnson
AT&T Research
Three applications of dynamic programming to network management

Nov 1
Elliot Anshelevich
Cornell Univ.
The Price of Stability for Network Design
Muthu @ Liverpool
Nov 8
Michael Littman
Rutgers Univ.
Algorithmic Problems in Sequential Decision Making

Eric away
Nov 15
Lisa Zhang
Bell Labs
Hardness of Undirected Edge Disjoint Path and Congestion

Nov 22
Boaz Barak
Extracting Randomness Using Few Independent Sources

Nov 29
Petros Drineas
The CUR Matrix Decomposition and its Applications to Algorithm Design and Massive Data Set Analysis

Dec 6
Matthew Andrews
Bell Labs,
Fairness and Quality-of-Service in Wireless Data Networks

Dec 13
Bruno Escoffier

Polynomial approximation of NP-hard problems: the differential ratio
Last Seminar for Fall 04. Muthu away.