Jakob Nordström: Rediscovering the Joys of Pebbling
Jakob Nordström, Theory Group, KTH CSC
Time: Wed 2013-04-17 12.10 - 13.00
Location: Room 4523, Lindstedtsvägen 5, 5th floor, KTH CSC
Lunch is served at 12:00 noon (register at http://doodle.com/8numsk6siw62e3z6 by Monday April 15 at 8 pm). 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.
Abstract
In the early 1970s, combinatorial pebble games played on directed acyclic graphs were introduced as a way of studying programming languages and compiler construction. These games later found a broad range of applications in computational complexity theory and were extensively studied up to ca 1985. Then they were mercifully forgotten, more or less...
Until during the last decade, when pebbling quite surprisingly turned out to be very useful in proof complexity. In this talk, we will describe the connections between the two settings and how tight they are, present an improved reduction, and discuss the gap that remains.
In order to use this reduction to obtain interesting results in proof complexity, one needs pebbling results with quite specific (and rather strong) properties. We will also discuss a new such result, that broke the 25-year hiatus in the pebbling literature by appearing in CCC ’10.
This seminar is intended to be completely self-contained. In particular, no prerequisites in proof complexity or pebbling are required. After the break, in the technical sequel we intend to have some fun and actually prove some pebbling time-space trade-off results.