Group:Lunch Meeting
Title: Space Lower Bounds by Pebble Games in Proof Complexity
Speaker: Bangsheng Tang University
Time: 2011-11-24 12:00-2011-11-24 14:00
Venue: FIT 1-222

Abstract:

Recently I'm reading materials in proof complexity, especially on lower bounds. There are three measures of a proof, the length, the width and the space. Many results have been derived about length and width and their relations. Recently space bounds have attracted a lot of attentions. The paper by Nordst rm and Ben-Sassen with title "Short Proofs May Be Spacious" discusses proving space lower bounds for refuting a specific kind of formulas by resolution. The main technique is to translate playing pebble games, which is an old object used to prove space lower bounds and space-time trade-offs, to resolutions, preserving the underlying difficulties, and then derive the lower bound for resolutions from the well-known lower bound for pebble games. I would like to try to describe the structure of the proof and share some of my understanding.