<p>Assume we want to refute an unsatisfiable CNF.  We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear relaxation until the polytope is empty.</p>

<p>For a polytope $P$ we consider $N_{+}(P)$ to be the polytope where all possible $LS_{+}$ cuts have been further applied.  We can always iterate the operator $N_{+}$ until the resulting polytope is empty.  The number of iterations required to reach the empty polytope is called the <em>rank</em> of the polytope.</p>

<p>Since each iteration increases the number of facet of a polynomial factor, a non constant number of iterations is out of question. </p>

<p>In the case of Gomory-Chvátal cuts, the usual PHP formula requires rank $\Omega(\log n)$, but there exists a refutation of polynomial size.  Such refutation essentially produces the empty polytope using only a small number of the facets from each iteration.</p>

<p><strong>My question is:</strong> does there exist a similar example for $LS_{+}$ cuts, i.e. a case where an short refutation exists but the rank is large?</p>

<p><strong>Update</strong>: The following paper shows (among other things) that a tautology with short refutation and linear rank would separate Tree-Like LS+ from general LS+ refutations.</p>

<p>Toniann Pitassi and Nathan Segerlind, "<a href="http://www.cs.toronto.edu/~toni/Papers/soda.ps">Exponential Lower Bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures</a>", SODA, 2009.   </p>

CC BY-SA 2.5
2010-10-20T17:13:54.510Z
I assume that LS cuts are Lovasz-Schrijver cuts ? might be helpful to clarify.
Suresh Venkat
CC BY-SA 2.5
2010-10-21T07:42:41.220Z
So basically you look for a hard tautology (different from PHP) that separates tree-like and dag-like LS+ ? Am I correct ?
Iddo Tzameret
CC BY-SA 2.5
2010-10-21T11:09:49.277Z
I don't know the status of rank size trade-offs in LS+. Of course a positive answer to this question is a step towards the separation you mention.  For context: consider PHP under Cutting Planes with Gomory-Chvátal cuts; in this case the short refutation is polynomial size and tree-like while the rank in $\Omega(\log n)$. This is non trivial since usually rank $r$ implies $n^r$ upper bounds, both in GC and LS.  Notice that as far as I know even such upper bound is unknown for LS+.  My question can be rephrased like: "given that such upper bound exists, it is optimal?".
MassimoLauria
CC BY-SA 2.5
2010-10-29T13:08:35.097Z
Apparently in SODA 2009, Pitassi and Segerlind proved rank/size trade-off for tree-like and LS and tree-like LS+. Thus Iddo's comment is completely correct.
MassimoLauria
CC BY-SA 2.5
2010-10-30T06:15:36.753Z
Do you want to update your question? (I have added the link to Toni and Nathan's paper.) Also if this is an open problem, we should add the [open-problem] tag.
Kaveh
<cc.complexity-theory><open-problem><integer-programming><proof-complexity>
Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?
MassimoLauria
# Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

(Asked by: username_0 on 2010-10-20)

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS\_{+}$ cuts) to its linear relaxation until the polytope is empty.

For a polytope $P$ we consider $N\_{+}(P)$ to be the polytope where all possible $LS\_{+}$ cuts have been further applied. We can always iterate the operator $N\_{+}$ until the resulting polytope is empty. The number of iterations required to reach the empty polytope is called the *rank* of the polytope.

Since each iteration increases the number of facet of a polynomial factor, a non constant number of iterations is out of question.

In the case of Gomory-Chvátal cuts, the usual PHP formula requires rank $\Omega(\log n)$, but there exists a refutation of polynomial size. Such refutation essentially produces the empty polytope using only a small number of the facets from each iteration.

**My question is:** does there exist a similar example for $LS\_{+}$ cuts, i.e. a case where an short refutation exists but the rank is large?

**Update**: The following paper shows (among other things) that a tautology with short refutation and linear rank would separate Tree-Like LS+ from general LS+ refutations.

Toniann Pitassi and Nathan Segerlind, "[Exponential Lower Bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures](http://www.cs.toronto.edu/~toni/Papers/soda.ps)", SODA, 2009.

**Tags:** cc.complexity-theory, open-problem, integer-programming, proof-complexity

> **Comments:**
> **username_1**: I assume that LS cuts are Lovasz-Schrijver cuts ? might be helpful to clarify.  
> **username_2**: So basically you look for a hard tautology (different from PHP) that separates tree-like and dag-like LS+ ? Am I correct ?  
> **username_0**: I don't know the status of rank size trade-offs in LS+. Of course a positive answer to this question is a step towards the separation you mention.  For context: consider PHP under Cutting Planes with Gomory-Chvátal cuts; in this case the short refutation is polynomial size and tree-like while the rank in $\Omega(\log n)$. This is non trivial since usually rank $r$ implies $n^r$ upper bounds, both in GC and LS.  Notice that as far as I know even such upper bound is unknown for LS+.  My question can be rephrased like: "given that such upper bound exists, it is optimal?".  
> **username_0**: Apparently in SODA 2009, Pitassi and Segerlind proved rank/size trade-off for tree-like and LS and tree-like LS+. Thus Iddo's comment is completely correct.  
> **username_3**: Do you want to update your question? (I have added the link to Toni and Nathan's paper.) Also if this is an open problem, we should add the [open-problem] tag.  

---

## 0 answers

