Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jordi Levy:

TR03-041 | 29th May 2003
Albert Atserias, Maria Luisa Bonet, Jordi Levy

On Chvatal Rank and Cutting Planes Proofs

We study the Chv\'atal rank of polytopes as a complexity measure of
unsatisfiable sets of clauses. Our first result establishes a
connection between the Chv\'atal rank and the minimum refutation
length in the cutting planes proof system. The result implies that
length lower bounds for cutting planes, or even for ... more >>>

ISSN 1433-8092 | Imprint