DIMACS/CS Light Seminar: Theoretical Computer Science
Spring 2009

Place:                   CoRE 431
Time:                   Wednesdays 11:00 -- 12:00 Noon
Contacts:               Mario Szegedy, Eric Allender, and Michael Saks
Index number:     
198:500:02  (46924)

See also the schedule for the MATH and CS seminar series. Data on previous semesters is also available.
NOTE to external speakers: Please see dimacs webpage for directions.

TITLE (link to abstracts)
January 21

No Seminar This Week
January 28
Eric Allender

Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds

February 4
Mark Braverman
Poly-logarithmic independence fools AC0 circuits

February 11
Pavel Hrubes
Arithmetic complexity of symmetric polynomials

February 18
Nikos Leonardos
Lower bounds on the randomized communication complexity of read-once functions

February 25
Mohammad Hossein Bateni
Improved approximation algorithms for prize-collecting problems

March 4

Organizers are out of town
No Seminar This Week
March 11
Russell Impagliazzo
An Axiomatic Approach to Algebrization

March 18

Spring Break
No Seminar This Week
March 25
David Steurer
Message Passing Algorithms and Improved LP Decoding
CoRE 301
April 1

DIMACS Workshop on Property Testing
No Seminar; consider registering for the workshop
April 8
Qi Cheng
A Deterministic Reduction for the Gap Minimum Distance Problem

April 15
Virginia Vassilevska
Detecting, Finding and Minimizing Weighted Triangles

April 22
Ramamohan Paturi
On the Complexity of Circuit Satisfiability
CoRE 301
April 29
Peter Richter
On the hitting times of quantum versus random walks
CoRE 301