Siu Man Chan: Pebble Games and Complexity
Tid: Må 2013-12-02 kl 12.00 - 15.00
Plats: Room 4523, Lindstedtsvägen 5, 5th floor
Medverkande: Siu Man Chan, Princeton University
- Lunch is served at 12:00 noon (register at
http://doodle.com/ievpvavz87imn4ng by Sunday Dec 1).
- The presentation starts at 12:10 pm and ends at 1 pm.
- Those of us who wish reconvene after a short break for ca two hours of
more technical discussions.
We will discuss space and parallel complexity, ranging from some classical
results which motivated the study, to some recent results concerning
combinatorial lower bounds in restricted settings. The recurring theme is
some pebble games. We will highlight some of their connections to Boolean
complexity and proof complexity.