All reports by Author Dmitrii V. Pasechnik:

__
TR03-052
| 13th May 2003
__

Stanislav Busygin, Dmitrii V. Pasechnik#### On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

__
TR01-103
| 14th December 2001
__

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik#### Complexity of semi-algebraic proofs

Revisions: 3

Stanislav Busygin, Dmitrii V. Pasechnik

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>