Proof complexity as a computational lens lecture 23: Size-space trade-offs for cutting planes (cont) скачать в хорошем качестве

Proof complexity as a computational lens lecture 23: Size-space trade-offs for cutting planes (cont)

Tuesday Feb 3, 2026 Proof complexity as a computational lens Lecture 23: Size-space trade-offs for cutting planes (cont.) (Jakob Nordström, University of Copenhagen and Lund University) In this lecture, we continue the proof of the result by [de Rezende, Nordström, and Vinyals '16] that there are size-space trade-offs for the cutting planes proof system where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and line space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. We focus on the main technical component in the proof, which is a simulation theorem saying that round-efficient communication protocols for lifted search problems can be converted to shallow parallel decision trees for the original search problem. For simplicity, we do the proof for standard deterministic communication, though the cutting planes trade-offs need a stronger version of the theorem for real communication. We give a detailed overview of the proof including the technical lemmas and how they fit together, but have to skip some of the more intricate combinatorial arguments due to time constraints. This is lecture 23 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