Proof complexity as a computational lens lecture 9: A general method for PC degree lower bounds скачать в хорошем качестве

Proof complexity as a computational lens lecture 9: A general method for PC degree lower bounds

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