<p>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}$.</p>

<p>If $\alpha(G^{\boxtimes n}) &lt; \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}$?</p>

CC BY-SA 3.0
2013-08-15T18:29:01.823Z
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 
CC BY-SA 3.0
2013-08-15T18:45:56.097Z
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.
Turbo
CC BY-SA 3.0
2013-08-15T18:48:58.690Z
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 
CC BY-SA 3.0
2013-08-15T22:17:47.453Z
I believe you may be able to use the reductions in [Tulsiani's paper](http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf) 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
CC BY-SA 3.0
2013-08-16T08:45:28.970Z
@SashoNikolov This is a good reference. It says any constant $k$ rounds can be done in $n^{O(k)}$ time and still get only $\vartheta$ as optimal solution. Seems like there should be a converse that in $n^{k}$ time, one cannot do more than $O(k)$ rounds. However that sounds hard.
Turbo
CC BY-SA 3.0
2013-08-16T15:11:57.417Z
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](http://arxiv.org/pdf/1111.0837v3.pdf) 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
CC BY-SA 3.0
2013-08-17T13:33:05.883Z
@SashoNikolov A related question. Supposing we have a better than $n^{\frac{1}{15}}$ approximation for a graph family, does that mean for that graph family we can compute clique in polynomial time?
Turbo
CC BY-SA 3.0
2013-08-17T14:12:54.203Z
http://www.cs.washington.edu/education/courses/cse533/05au/feige-kilian-conference.pdf says approximating clique to $n^{\frac{1}{15}}$ is hard under a complexity conjecture and http://people.csail.mit.edu/madhu/papers/1994/bellare.pdf mentions a conjecture in footnote that Lovasz theta approximates clique to $n^{\frac{1}{2}}$ ($\underline{\mbox{where is this conjecture from and what progress has been made}}$?) So if the conjecture is true, lifting $15$ to $2$ should suffice showing no such function exists under complexity assumptions for general graphs.

How about for special graph families?
Turbo
CC BY-SA 3.0
2013-08-17T17:34:45.930Z
@JAS: It is known that approximating clique to $n^{0.9999}$ is NP-hard: http://en.wikipedia.org/wiki/Clique_problem
Mahdi Cheraghchi
CC BY-SA 3.0
2013-08-17T17:37:57.023Z
Oh the results I am quoting are old :(

I am also thinking since clique and Indep set are complementary, approx results should be similar for both.
Turbo
CC BY-SA 3.0
2013-08-17T17:38:46.083Z
That's right...
Mahdi Cheraghchi
CC BY-SA 3.0
2013-08-17T17:40:20.520Z
@MCH So does that somehow lead to any further info about Lovasz Theta optimality?
Turbo
CC BY-SA 3.0
2013-08-18T16:36:10.847Z
For one, it shows that Lovasz theta is not a good approximation unless $P=NP$.
Mahdi Cheraghchi
<graph-theory>
On Lovasz theta function
Turbo
# On Lovasz theta function

(Asked by: username_0 on 2013-08-15)

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

**Tags:** graph-theory
> **Comments:**
> **username_1**: 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".  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: I believe you may be able to use the reductions in [Tulsiani's paper](http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf) 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  
> **username_0**: @SashoNikolov This is a good reference. It says any constant $k$ rounds can be done in $n^{O(k)}$ time and still get only $\vartheta$ as optimal solution. Seems like there should be a converse that in $n^{k}$ time, one cannot do more than $O(k)$ rounds. However that sounds hard.  
> **username_2**: 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](http://arxiv.org/pdf/1111.0837v3.pdf) 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.  
> **username_0**: @SashoNikolov A related question. Supposing we have a better than $n^{\frac{1}{15}}$ approximation for a graph family, does that mean for that graph family we can compute clique in polynomial time?  
> **username_0**: http://www.cs.washington.edu/education/courses/cse533/05au/feige-kilian-conference.pdf says approximating clique to $n^{\frac{1}{15}}$ is hard under a complexity conjecture and http://people.csail.mit.edu/madhu/papers/1994/bellare.pdf mentions a conjecture in footnote that Lovasz theta approximates clique to $n^{\frac{1}{2}}$ ($\underline{\mbox{where is this conjecture from and what progress has been made}}$?) So if the conjecture is true, lifting $15$ to $2$ should suffice showing no such function exists under complexity assumptions for general graphs.  How about for special graph families?  
> **username_3**: @JAS: It is known that approximating clique to $n^{0.9999}$ is NP-hard: http://en.wikipedia.org/wiki/Clique_problem  
> **username_0**: Oh the results I am quoting are old :(  I am also thinking since clique and Indep set are complementary, approx results should be similar for both.  
> **username_3**: That's right...  
> **username_0**: @MCH So does that somehow lead to any further info about Lovasz Theta optimality?  
> **username_3**: For one, it shows that Lovasz theta is not a good approximation unless $P=NP$.  

---

## 0 answers

