Summer School on Applied Logic: Proof Complexity Notes

• Paul Beame's Slides: Translating Bounded Arithmetic Provability to Frege and Extended Frege Proofs (30 pages)

• Paul Beame's Slides: Exponential Size Lower Bounds for Bounded-Depth Frege Proofs of the Pigeonhole Principle: Part I (38 pages)

• Paul Beame's Slides: Exponential Size Lower Bounds for Bounded-Depth Frege Proofs of the Pigeonhole Principle: Part II: Switching Lemmas (28 pages)

• Paul Beame's Slides: Adding Axioms to Bounded-Depth Frege Proof Systems (29 pages)

• Paul Beame's Slides: Nullstellensatz Proof Systems (13 pages)

• Sam Buss's Slides: Part 1: Bounded Arithmetic (42 pages)

• Sam Buss's Slides: Part 2: Propositional Proofs and Two Translations from Bounded Arithmetic (30 pages)

• Sam Buss's Slides: Part 3: Natural Proofs and Interpolation Theorems (35 pages)

• Alasdair Urquhart's Survey Paper: The Complexity of Propositional Proofs (45 pages)