<p>Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and produce for this graph a certificate for the SDP which corresponds to having found a clique of size $n^\alpha$ in $G_1$ for some $\alpha \in (0,1]$. </p>

<p>Now using this certificate (or any other means!) is it possible to construct another graph $G_2$  of size $N$ (might be necessary that $N&gt;n$) and a certificate for it for this same SDP which would correspond to having found a $N^{ 1-\epsilon }$ size clique in $G_2$ for some $1 - \epsilon &gt; \alpha$? (its okay even if $G_2$ is shown to exist in some probabilistic sense) </p>

<p>Are there examples of doing such a blow-up of the objective value for a Max-Clique SDP?</p>

<hr>

<p>Not sure if its immediately related but putting this out here : Is there any obvious reason why this very famous paper <a href="http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf" rel="nofollow">http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf</a> does not deal with Max-Clique? Isn't it true that the complement of the Max-Independent-Set integrality gap instance does <em>not</em> give the integrality gap instance of Max-Clique? </p>

CC BY-SA 3.0
2016-06-01T08:58:11.613Z
Please ask only one question per post. You can ask the second question separately, with a link to this question.
Jan Johannsen
CC BY-SA 3.0
2016-06-01T13:18:54.147Z
Yes, but I thought this reference helps put the question in context..
Student
<cc.complexity-theory><np-hardness><complexity-classes><approximation-hardness><sum-of-squares>
About increasing the objective values of certificates for Max-Clique SDP
Student
# About increasing the objective values of certificates for Max-Clique SDP

(Asked by: username_0 on 2016-05-31)

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G\_1$ of size $n$ and produce for this graph a certificate for the SDP which corresponds to having found a clique of size $n^\alpha$ in $G\_1$ for some $\alpha \in (0,1]$.

Now using this certificate (or any other means!) is it possible to construct another graph $G\_2$ of size $N$ (might be necessary that $N>n$) and a certificate for it for this same SDP which would correspond to having found a $N^{ 1-\epsilon }$ size clique in $G\_2$ for some $1 - \epsilon > \alpha$? (its okay even if $G\_2$ is shown to exist in some probabilistic sense)

Are there examples of doing such a blow-up of the objective value for a Max-Clique SDP?

---

Not sure if its immediately related but putting this out here : Is there any obvious reason why this very famous paper <http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf> does not deal with Max-Clique? Isn't it true that the complement of the Max-Independent-Set integrality gap instance does *not* give the integrality gap instance of Max-Clique?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, approximation-hardness, sum-of-squares
> **Comments:**
> **username_1**: Please ask only one question per post. You can ask the second question separately, with a link to this question.  
> **username_0**: Yes, but I thought this reference helps put the question in context..  

---

## 0 answers

