On the Width of Semialgebraic Proofs and Algorithms
研究了半代数证明系统和整数规划中割平面法的宽度，对随机k-CNF和完美匹配等组合原理证明了宽度下界，并发现了宽度与秩之间的超临界权衡。
In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvátal cutting planes and Lovász-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimization problems. We establish a “supercritical” trade-off between width and rank, that is we give an example in which small width proofs are possible but require exponentially many rounds to perform them.