DIMACS/CS Light Seminar: Theoretical Computer Science
Fall 2005

Place:                   Core 431.
Time:                   Tuesdays 2:00 -- 3:00 PM
Contact:               Eric Allender
Index number:     
198:500:01  ( 30317 )

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.

DIMACS CS Theory Light Seminar
TITLE (link to abstracts)
Sept 6
Adi Avidor
Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT

Sept 13
Ilan Newman
Testing Orientations

Sept 20
Mario Szegedy
The quantum adversary method and classical formula size lower bounds

Sept 27
Joel Ratsaby
Information and Learning

Oct 4
Henning Schnoor
Generalized Modal Satisfiability

Oct 11
Saugata Basu
Efficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets

Oct 18
Pierre McKenzie
Incremental branching programs

Oct 25

No talk because of FOCS
Nov 1
Andrej Bogdanov
Pseudorandom generators for low degree polynomials

Nov 8
Dror Weitz
Glauber dynamics on trees: Boundary conditions and mixing time
Talk will be held in CoRE 301 (Conference room A); regular DIMACS seminar room is unavailable
Nov 15
James R. Lee
Trees and Markov convexity

Nov 22
Sambuddha Roy
The directed planar reachability problem

Nov 29
Rohan Fernandes
Upper and Lower Bounds in Sensor Network Bootstrapping

Dec 6
Joe Kilian
Combining Cryptographic Primitives

Dec 13
Eric Allender
On the Complexity of Numerical Analysis

Dec 20
Dieter van Melkebeek
A Generic Time Hierarchy for Semantic Models With One Bit of Advice
Last Seminar for Fall 05