ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > DMITRII V. PASECHNIK:
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

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


TR01-103 | 14th December 2001
Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

Complexity of semi-algebraic proofs

Revisions: 3

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




ISSN 1433-8092 | Imprint