All reports by Author Arist Kojevnikov:

__
TR07-010
| 4th January 2007
__

Arist Kojevnikov#### Improved Lower Bounds for Resolution over Linear Inequalities

Revisions: 1

__
TR03-012
| 21st January 2003
__

Edward Hirsch, Arist Kojevnikov#### Several notes on the power of Gomory-Chvatal cuts

Arist Kojevnikov

We continue a study initiated by Krajicek of

a Resolution-like proof system working with clauses of linear

inequalities, R(CP). For all proof systems of this kind

Krajicek proved an exponential lower bound that depends

on the maximal absolute value of coefficients in the given proof and

the maximal clause width.

Edward Hirsch, Arist Kojevnikov

We prove that the Cutting Plane proof system based on

Gomory-Chvatal cuts polynomially simulates the

lift-and-project system with integer coefficients

written in unary. The restriction on coefficients can be

omitted when using Krajicek's cut-free Gentzen-style extension

of both systems. We also prove that Tseitin tautologies

have short proofs in ...
more >>>