Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-010 | 28th January 2016 18:36

On the Width of Semi-Algebraic Proofs and Algorithms

RSS-Feed




TR16-010
Authors: Alexander Razborov
Publication: 28th January 2016 18:37
Downloads: 1350
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