[Proof Complexity] a preprint

[Alexander Razborov]

Dear Colleagues,

In case you are interested, a new preprint of mine ``On the Width of 
Semi-Algebraic Proofs and Algorithms'' has been just released at

http://people.cs.uchicago.edu/~razborov/research.html

The abstract is attached below. Any comments and remarks are
very welcome.

Sasha

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%