Discrete Math/Theory of Computing Seminar

Rutgers University, Piscataway, N.J.

Fall 2002

Organizers: Eric Allender and Michael Saks

Current semester

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!