# About the interpretation of the SOS hardness results of the planted Max-Clique problem

One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the planted-Max-Clique problem and the second one is improving the detection threshold from $n^{1/3}$ in the first paper to $n^{1/2}$.

• Does any of these results imply or do they implicitly contain the hardness threshold for say just the Max-Clique problem w.r.t even just the degree-4 SOS?

Or are both these results totally specific to the planted problem and say nothing about the Max-Clique?

If I say look at the corollary 2.1 (bottom of page 10) in http://arxiv.org/pdf/1502.06590v1.pdf then this seems to be a hardness threshold for just the Max-Clique problem but I am not feeling very sure since the authors never put in these same words. Am I missing something? The same can be said about Theorem 1.1 (page 2) in the second paper.

If one sees the section 2.4 in the second paper, where they construct the SDP witness it feels that their construction would make sense only in the "planted" setting and then contrary to my feeling from theorem 1.1 now I start feeling that the result applies only with planting.

• You might be interested in this: eccc.hpi-web.de/report/2016/058. – Yuval Filmus Apr 12 '16 at 22:39
• Yes. I saw this within minutes of when it was uploaded today afternoon. Wonder what is the next question to answer here! – gradstudent Apr 13 '16 at 2:30

• If one knows that with high probability (even just non-zero probability) the hard graphs exist then isn't it immediately obvious that one can always pick those hard graphs adversarially to trip SOS? (...ofcourse I guess what is open is to see if the $\sqrt{n}$ can be improved to the UGC bound of Max-Clique for 4 or higher degree SOS..) – Anirbit Apr 13 '16 at 21:06