TITLE:  Rank Lower Bounds for Generic Cutting-Plane Proof Systems

SPEAKER:  Sebastian Pokutta - faculty candidate

ABSTRACT:

We introduce a natural abstraction of cutting-plane proof systems, which subsumes well-known operators such as Gomory-Chvátal, lift-and-project, Sherali-Adams, Lovász-Schrijver, and split cuts. We exhibit a family of polytopes without integral points contained in the n-dimensional 0/1-cube that has rank Omega(n/ log n) for any proof system in our class. In fact, we show that whenever a specific cutting-plane based proof system has (maximal) rank n
on a particular family of instances, then any cutting-plane proof system in our class has rank Omega(n/ log n) for this family. We also construct a new cutting-plane proof system that has worst-case rank O(n/ log n) for any polytope without integral points, implying that the new universal lower bound is virtually tight.
(joint work with Andreas S. Schulz)