Talk slides
Five Lecture Slides
Proof Complexity Survey
Boot Camp for Special Program on Satisfiability:
Theory, Practice and Beyond
Simons Institute for the Theory of Computing, Berkeley
February 3, 2021.
Slides for the boot camp are available here: The first four were prerecorded videos; the fifth was presented via zoom. The videos are available from the Simons Institute.
Proof Complexity:
Part A: Introduction, Frege proofs, Abstract proof systems
and Resolution
Download
talk slides.
Proof Complexity:
Part B: Propositional Pigeonhole principle,
Upper and Lower Bounds
Download
talk slides.
Proof Complexity:
Part C: Resolution and CDCL
Download
talk slides.
Proof Complexity:
Part D: Pseudo-Boolean and Algebraic Proof Systems and
and Automatizability
Download
talk slides.
Proof Complexity:
CDCL and Restarts; (Semi)Algebraic Systems; Constant depth Frege
(Live Zoom presentation)
Download
talk slides.