# On Lovasz theta function

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}$?

• 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". – Peter Shor Aug 15 '13 at 18:29
• 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. – 1.. Aug 15 '13 at 18:45
• 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. – Peter Shor Aug 15 '13 at 18:48
• 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 – Sasho Nikolov Aug 15 '13 at 22:17
• 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. – Sasho Nikolov Aug 16 '13 at 15:11