Organizers:
Eric Allender
and
Michael
Saks
September 11
Speaker: Eric Allender, Rutgers University
Title:
The circuit complexity of division
Time:
4:30-5:30
Place:
CORE 431
September 18
Speaker: Michael Elkin, Weizmann Institute
of Science, Rehovot, Israel
Title:
Construction of (1+epsilon,beta)-Spanners
on General Graphs
Time:
4:30-5:30
Place:
CORE 431
September 25
Speaker: Mario Szegedy, Rutgers University
Title:
Computing boolean functions from multiple faulty copies of input bits
Time:
4:30-5:30
Place:
CORE 431
October 2
Speaker: Ehud Friedgut, Hebrew University, Jerusalem
Title:
Ramsey properties of random graphs:
A sharp thresholds via Szemeredi-regularity
in hypergraphs.
Time:
4:30-5:30
Place:
Hill 705 (NOTE ROOM CHANGE)
October 9
NO SEMINAR:
DIMACS Mixer at NEC Research
October 16
Speaker: Jozsef Balogh, AT&T Research
Title:
Monotone Graph Properties
Time:
4:30-5:30
Place:
CORE 431
October 23
Speaker:
Alexander Razborov, Institute for Advanced Study and Steklov Math. Institute
Title:
Proof Complexity of Pigeonhole Principles
Time:
4:30-5:30
Place:
CORE 431
October 30
Speaker:
Venkatesh Srinivasan, DIMACS
Title:
On the advantage of random assignment
Time:
4:30-5:30
Place:
CORE 431
November 6
Speaker: Peter Winkler, Bell Laboratories
Title:
Incremental Sampling
Time:
4:30-5:30
Place:
HILL 705 (NOTE ROOM CHANGE)
November 13
Speaker: David Galvin, Rutgers University
Title:
Phase transition in the hard-core model on Z^d
Time:
4:30-5:30
Place:
HILL 705 (NOTE ROOM CHANGE)
November 20
Speaker: Xiaodong Sun, Rutgers University
Title:
Space lower bounds for distance approximation in the data stream model
Time:
4:30-5:30
Place:
CORE 431
November 27
Speaker: Rafail Ostrovsky, Telcordia Technologies
Title:
Dimension reduction in the Hamming cube and its applications
Time:
4:30-5:30
Place:
CORE 431
December 4
NO SEMINAR:
DIMACS workshop on Codes and Complexity
Have a nice break!