5
$\begingroup$

Given a graph $G$, it is known independence number $\alpha(G)$ and Lovasz theta $\vartheta(G)$ satisfy the inequality, $\alpha(G^{\boxtimes n}) \leq \vartheta(G)^{n}$.

If $\alpha(G^{\boxtimes n}) < \vartheta(G)^{n}$, under plausible complexity theory conjectures, is it possible to have any other polynomial time computable function $\psi(G)$ that works for all graphs $G$ (or special family of graphs) and that produces numbers satisfying the inequality $\alpha(G^{\boxtimes n}) \leq \psi(G)^{n} \leq \psi(G^{\boxtimes n}) \leq \vartheta(G)^{n}$?

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ Yes. You could use a function that is equal to $\vartheta(G)$ except for a finite list of exceptions. I suspect you would consider this "cheating". $\endgroup$
    – Peter Shor
    Aug 15 '13 at 18:29
  • $\begingroup$ Yes. However this is something I would not want:) I thought I read somewhere that no other non-trivial function is possible. I do not know the reference. That is no other non trivial approximation to independence number is possible in polynomial time. $\endgroup$
    – Mr.
    Aug 15 '13 at 18:45
  • 4
    $\begingroup$ I believe no other non-trivial function is known. It may be known that no other function given by a semidefinite program is possible (this would be a fantastic result) but the tools of complexity theory are not yet capable of proving that no other polynomial-time computable function is possible. $\endgroup$
    – Peter Shor
    Aug 15 '13 at 18:48
  • 4
    $\begingroup$ I believe you may be able to use the reductions in Tulsiani's paper to show that $O(1)$ levels in the Lasserre hierarchy do not provide a significant improvement over $\vartheta$ (which corresponds to the first level of Lasserre). Note that the Lasserre hierarchy relaxations are multiplicative just like $\vartheta$. And they are stronger than the Lovasz-Schrijver SDP hierarchy $\endgroup$
    – Sasho Nikolov
    Aug 15 '13 at 22:17
  • 2
    $\begingroup$ Bear in mind that $k$-th level Lasserre has $n^{\Omega(k)}$ variables. One way you can approach the question from your last comment is: what is the SDP extension complexity of the projection onto the singleton variables of the $k$-th level Lasserre relaxation of the stable set polytope. SDP extension complexity lower bounds remain hard afaik, although arguably not as inaccessible as other complexity questions. $\endgroup$
    – Sasho Nikolov
    Aug 16 '13 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.