Organizers:
Eric Allender
and
Michael
Saks
September 10
Speaker: Russell Impagliazzo, University of California at San Diego
Title:
A switching lemma for small restrictions
and lower bounds for k-DNF Resolution
Time:
4:30-5:30
Place:
CORE 431
September 17
Speaker: Jozsef Beck, Rutgers University
Title:
A variant of the Heilbronn's triangle problem:
the Motzkin-Schmidt strip problem
Time:
4:30-5:30
Place:
CORE 431
September 24
Speaker: Maria Chudnovsky, Princeton University
Title:
The Strong Perfect Graph Theorem
Time:
4:30-5:30
Place:
HILL 705 (Note room change)
October 1
NO SEMINAR
DIMACS workshop on geometric graph theory
October 8
Speaker: Irit Dinur, NEC Research Institute, Princeton
Title:
The hardness of 3-uniform hypergraph coloring
Time:
4:30-5:30
Place:
HILL 705 (Note room change)
October 15
Speaker: Michael Capalbo, DIMACS
Title:
Explicit unique-neighbor expanders
Time:
4:30-5:30
Place:
HILL 705 (Note room change)
October 22
Speaker: NO SEMINAR (DIMACS Mixer seminar at Telcordia)
October 29
Speaker: Mikkel Thorup, ATT Research, Florham Park, NJ
Title:
On Distance Oracles and Routing in Graphs
Time:
4:30-5:30
Place:
CORE 431
November 5
Speaker: Gabor Tardos, Renyi Institute, Budapest
Title:
Locally planar graphs
Time:
4:30-5:30
Place:
HILL 705 (Note room change)
(The talk originally scheduled for this date, by Kobbi Nissim, is postponed
to a later date)
November 12
Speaker: Amit Chakrabarti, Institute for Advanced Study, Princeton, NJ
Title:
Informational Complexity and Lower Bounds in Communication Complexity
Time:
4:30-5:30
Place:
CORE 431
November 19
Speaker: Kobbi Nissim (postponed from November 5)
Title:
Revealing information while preserving privacy
Time:
4:30-5:30
Place:
HILL 705 (Note room change)
November 26
Speaker: Michael Langberg
Title:
Graphs with tiny vector
chromatic number and huge chromatic numbers
Time:
4:30-5:30
Place:
CORE 431
December 3
Speaker: Oded Regev, Institute for Advanced Study, Princeton
Title:
Quantum Computation and Lattice Problems
Time:
4:30-5:30
Place:
CORE 431
December 10
Speaker: Detlef Ronneburger
Title:
Power from random strings
Time:
4:30-5:30
Place:
CORE 431
Have a nice break!