Proof complexity as a computational lens lecture 18: PCR space vs. width (cont.); NS size vs. degree
Автор: MIAO Research
Загружено: 2026-01-10
Просмотров: 19
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
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
![WHOOPS '25: Сквозная проверка для решения подграфов [демо] (Ён Киам Тан)](https://image.4k-video.ru/id-video/WhO8Tm7M6Hw)