Abstract:

We introduce a natural abstraction of propositional proof systems that are based on cutting planes. This new class of proof systems covers well-known operators including Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts, Lovász-Schrijver cuts, and split cuts. The rank of such a proof system corresponds to the number of rounds needed to show the nonexistence of integral solutions to a system of linear inequalities. We present a family of polytopes in the unit cube without integral points and show that it has a high rank for any proof system in this class. In fact, we prove that whenever a specific cutting-plane proof system has maximal rank on a particular family of instances, then the rank of any cutting-plane proof system is close to maximal. This result essentially implies that the rank of worst-case examples does not depend on specific cutting-plane proof systems; it is intrinsic to the respective family of instances. (Joint work with Sebastian Pokutta.)

The lecture can be attended without previous notice.