Fall 2010 Seminar Series

DATE: November 18th
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following in same room

SPEAKER:
Sebastian Pokutta

TITLE
On the Rank of Generic Cutting-Plane Proof Systems

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 Ω(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 Ω(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.