# 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

## 1 Answer

The planted clique problem and the maximum clique problem are different problems, though the former was introduced as an average case version of the latter. A paper addressing the planted clique problem doesn't address the maximum clique problem, and vice versa.

In particular, the papers you mention concern the planted clique problem, not the maximum clique problem.

• Yes! But you see why theorem 2.1 in the first and theorem 1.1 in the second look like theorems about Max-Clique rather than about the planted thing? These seem pretty general statements with no reference to the planting. For Max-Clique since the SDP doesn't change from the one in these papers why doesn't the same certificate as constructed in these papers also imply the same thresholds for the Max-Clique problem? – gradstudent Apr 13 '16 at 2:21
• The results you mention are all probabilistic. They only hold with high probability. – Yuval Filmus Apr 13 '16 at 5:33
• Yes. But isn't that enough? What do you think is missing? – gradstudent Apr 13 '16 at 13:42
• The witnesses only exist with high probability over the choice of the graph. The results don't say anything about arbitrary (adversarial) graphs. – Yuval Filmus Apr 13 '16 at 14:29
• 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