Proof Complexity

          @misc{ scivideos_16967,
            doi = {},
            url = {https://simons.berkeley.edu/talks/proof-complexity},
            author = {},
            keywords = {},
            language = {en},
            title = {Proof Complexity},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {16967 see, \url{https://scivideos.org/index.php/Simons-Institute/16967}}
          }
          

Abstract

These videos provide an introduction to proof complexity, especially from the point of view of satisfiability algorithms.  There are four videos.  Part A introduces proof complexity, and discusses Frege proofs, abstract proof systems, resolution, and extended Frege proofs and extended resolution.  Part B discusses the propositional pigeonhole principle, and upper and lower bounds on the complexity of proofs of the pigeonhole principle in the extended Frege proof system, the Frege proof systems, and resolution. Part C discusses the CDCL satisfiability algorithms from the point of view from proof complexity, including discussion of clause learning, trivial resolution, unit propagation, restarts, and RUP and (D)RAT proof traces.  Part D discusses cutting planes, the Nullstellsatz and Polynomial Calculus proof systems and concludes with a short discussion of automatizability. Parts B and C are independent of each other. Part D has a modest dependency on Part B, but can also be watched independently.