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.

DATE
  SPEAKER
TITLE (link to abstracts)
Notes
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
IAS
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
Minimization


Nov 22
Boaz Barak
IAS
Extracting Randomness Using Few Independent Sources

Nov 29
Petros Drineas
RPI
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.