Proof complexity as a computational lens lecture 16: PCR space lower bounds for random CNF formulas скачать в хорошем качестве

Proof complexity as a computational lens lecture 16: PCR space lower bounds for random CNF formulas

Thursday Dec 18, 2025 Proof complexity as a computational lens Lecture 16: Polynomial calculus space lower bounds for random CNF formulas (Jakob Nordström, University of Copenhagen and Lund University) In this lecture, we discuss space complexity for polynomial calculus. We review the literature on space complexity for polynomial calculus with and without dual variables (PCR and PC, respectively), which has mostly focused on monomial space. Most of the lecture is then spent on showing optimal, linear, monomial space lower bounds in PCR for refuting random k-CNF formulas for k greater than or equal to 4 as established by [Bonacina and Galesi '15] (except we follow the exposition in [Lauria, Mikša, Nordström, and Vinyals '26]). This is lecture 16 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