Proof complexity as a computational lens lecture 18: PCR space vs. width (cont.); NS size vs. degree скачать в хорошем качестве

Proof complexity as a computational lens lecture 18: PCR space vs. width (cont.); NS size vs. degree

Friday Jan 9, 2026 Proof complexity as a computational lens Lecture 18: PCR space vs. resolution width (cont.); size-degree trade-offs for Nullstellensatz (Jakob Nordström, University of Copenhagen and Lund University) In this lecture, we conclude the proof of the theorem by [Galesi, Kołodziejczyk, and Thapen '25] that the monomial space required to refute a k-CNF formula is at least the square root of the resolution refutation width. We review the key definitions and lemmas in last lecture, and then state and prove the final lemmas required to establish the theorem. In the second half of the lecture, we talk about trade-offs between size and degree for Nullstellensatz. These trade-off results by [de Rezende et al. '21] are obtained by studying pebbling formulas and proving that time and space for reversible pebbling strategies for a directed acyclic graph (DAG) G correspond exactly to Nullstellensatz size and degree of refutations of the pebbling formula for G. This is lecture 18 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