Proof complexity as a computational lens lecture 21: Cutting planes and random CNF formulas скачать в хорошем качестве

Proof complexity as a computational lens lecture 21: Cutting planes and random CNF formulas

Thursday Jan 29, 2026 Proof complexity as a computational lens Lecture 21: Cutting planes lower bounds for random CNF formulas (Kilian Risse, Lund University) In this lecture, we study the complexity of refuting random CNF formulas in the cutting planes proof system. It has been known for decades that certifying unsatisfiability of randomly sampled k-CNF formulas for constant k (and large enough density of clauses compared to variables) is exponentially hard for resolution and polynomial calculus, but the corresponding problem for cutting planes has remained open. In a breakthrough, [Hrubeš and Pudlák '17] and independently [Fleming, Pankratov, Pitassi, and Robere '17] proved that cutting planes refutations of random CNF formulas of logarithmic width require exponential length. We cover the much simplified proof of this result by [Sokolov '24], which is based on a novel bottleneck counting argument, and discuss some of the many open problems that remain (such as establishing lower bounds for CNF formulas of constant width). This is lecture 21 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