Estonian Winter School in Computer Science 2012This 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
Background materialPart 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:
|