Group:Algorithms, Complexity and Cryptography Group
Title: Space Lower Bounds by Pebble Games in Proof Complexity
Speaker: Bangsheng Tang University
Time: 2011-12-23 14:00-2011-12-23 15:30
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 Nordstrom and Ben-Sasson with title "Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution" 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.

This talk is the continuation of the one I gave at the lunch meeting a few weeks ago, in which I defined Pebbling Formula, Resolution Pebbling Game, Black-White Pebble Game and gave the structure of the proof. I will quickly repeat the definitions and give more details on the proofs.



Short Bio: