Proof complexity as a computational lens lecture 9: A general method for PC degree lower bounds
Автор: MIAO Research
Загружено: 2025-11-26
Просмотров: 28
Tuesday Nov 25, 2025
Proof complexity as a computational lens
Lecture 9: A general method for polynomial calculus degree lower bounds: Applications
(Jakob Nordström, University of Copenhagen and Lund University)
In this lecture, we show how many lower bounds on polynomial calculus proof degree, and hence also on proof size, can be obtained in a unified way by using the generalized constraint-variable incidence graphs (CVIGs) in [Mikša and Nordström '24] and constructing CVIGs that are good enough expanders.
The actual proof that CVIGs with good enough expansion imply lower bound polynomial calculus degree is presented in next lecture.
This is lecture 9 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: End-to-end verification for subgraph solving [demo] (Yong Kiam Tan)](https://ricktube.ru/thumbnail/WhO8Tm7M6Hw/mqdefault.jpg)
