Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-010 | 28th January 2016 18:36

#### On the Width of Semi-Algebraic Proofs and Algorithms

TR16-010
Authors: Alexander Razborov
Publication: 28th January 2016 18:37
Keywords:

Abstract:

In this paper we initiate the study of width in semi-algebraic proof systems
and various cut-based procedures in integer programming. We focus on two
important systems: Gomory-Chv\'atal cutting planes and
Lov\'asz-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 an ultimate'' trade-off between width and
rank, that is give an example in which small width proofs are possible but
require {\em exponentially} many rounds to perform them.

ISSN 1433-8092 | Imprint