[Proof Complexity] Survey paper on proof complexity

[Jakob Nordstrom]

Dear colleagues,

This is to announce that I have now finished (what is hopefully very close
to) the camera-ready version of my survey paper "Pebble Games, Proof
Complexity, and Time-Space Trade-offs," to be published soon in Logical
Methods in Computer Science. The abstract follows below.

For now, this paper can be downloaded from the address
http://www.csc.kth.se/~jakobn/research/LMCSsurvey.pdf .

If you are interested in reading the survey (and solving some of the many
open problems discussed in it!), I would be extremely grateful if you
could send me comments about any typos, omissions, misattributions, or
possibly even more serious errors that you discover. Unfortunately, if the
final pass over the paper convinced me about anything then that is that
there are bound to remain many more annoying mistakes than I have already
found...

With best regards,
Jakob Nordstrom


ABSTRACT

Pebble games were extensively studied in the 1970s and 1980s in a number
of different contexts. The last decade has seen a revival of interest in
pebble games coming from the field of proof complexity. Pebbling has
proven to be a useful tool for studying resolution-based proof systems
when comparing the strength of different subsystems, showing bounds on
proof space, and establishing size-space trade-offs. This is a survey of
research in proof complexity drawing on results and tools from pebbling,
with a focus on proof space lower bounds and trade-offs between proof size
and proof space.


Jakob Nordström, Assistant Professor
KTH Royal Institute of Technology
Osquars backe 2, SE-100 44 Stockholm, Sweden
Phone: +46 8 790 69 19 (office), +46 70 742 21 98 (cell)
http://www.csc.kth.se/~jakobn/