*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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)
