Estonian Winter School in Computer Science 2012

This page contains information related to the course in proof complexity I taught at the Estonian Winter School in Computer Science (EWSCS '12) on February 26 – March 2 in Palmse, Estonia.

Slides

• Lecture 1 (slides last revised February 27, 2012)
• Lecture 2 (slides last revised February 28, 2012)
• Lecture 3 (slides last revised March 1, 2012)
• Lecture 4 (slides last revised March 1, 2012)

Background material

Part of the material I lectured on can be found in the paper Pebble Games, Proof Complexity, and Time-Space Trade-offs, which is a survey of proof complexity with a very heavy bias towards proof space lower bounds and time-space trade-offs for resolution-based proof systems.

I also used material from the course Current Research in Proof Complexity given at KTH during the winter of 2011/12. In particular, the scribe notes for lectures 9 and 11 contain all the details that we skipped or glossed over in the final two lectures.

A very selective pick of some other surveys of proof complexity which might be useful is:

• Nathan Segerlind: The Complexity of Propositional Proofs. Perhaps the most recent general-purpose survey of proof complexity.
• Jakob Nordström: Proof Complexity and Resolution. Chapter 4 of the lecturer's PhD thesis with a brief overview of proof complexity in general and resolution in particular.
• Paul Beame: Proof Complexity. Lecture notes from an IAS summer school with very good coverage of proof complexity. Note that some of the "if pigs can fly" style of results appear to be slightly misstated, but corrected versions can be found in the PhD thesis above.