Proof complexity as a computational lens lecture 28: Summary and outlook for future research

Описание: Friday Feb 27, 2026
Proof complexity as a computational lens
Lecture 28: Final lecture; summary of material covered and outlook for future research
(Jakob Nordström, University of Copenhagen and Lund University)

In this lecture, we summarize the material covered in the lectures of the course "Proof complexity as a computational lens"; highlight some open research problems; and also review some areas of proof complexity that we did not discuss at all during the course.

We give an overview of the most important results on the proof systems resolution, Nullstellensatz, polynomial calculus, and cutting planes that were covered in the course. We discuss not only proof size lower bounds, but also space complexity and trade-offs between different proof complexity measures, and also touch briefly on connections to SAT solving, Gröbner basis computations, and pseudo-Boolean solving.

We then review some proof systems that we did not have time to discuss during the course, although they would fit nicely into the theme of proof complexity as a computational lens, namely stabbing planes, Sherali-Adams, sum-of-squares, and resolution over parities. We also briefly mention proof systems like Frege, bounded-depth Frege, extended Frege, and the ideal proof system, and also talk about the related area of bounded arithmetic in logic. Finally, we list some applications of proof complexity in other areas of computational complexity theory, and also spend some time on discussing the use of proof complexity for designing certifying combinatorial solvers that generate machine-verifiable proofs of correctness for their computations, also known as proof logging, and what new proof rules have been introduced in such proof system.

Throughout the lecture, we try to highlight open research problems and interesting directions for future research.

This is the 28th and final lecture on the course "Proof complexity as a computational lens" (https://jakobnordstrom.se/teaching/pr...) given during the winter of 2025/26 at the University of Copenhagen and Lund University.


For more information about MIAO seminars and/or lectures, please visit https://jakobnordstrom.se/miao-seminars/ , or go to https://jakobnordstrom.se/miao-group/ to read more about the MIAO group.

#ProofComplexity