On the integrality gap of degree-4 sum of squares for planted clique

Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω log (n) added to an Erdős-Rényi graph G ∼ G(n,1 2 ), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω(n). By contrast, information theoretically, one can recover planted cliques so long as ω log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless ω n/ polylog n, improving on the bound ω n1/3 due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of References [2, 25, 27].

Original languageEnglish (US)
Article number28
JournalACM Transactions on Algorithms
Volume14
Issue number3
DOIs
StatePublished - Jul 2018

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Planted clique
  • Random matrices
  • Sum of Squares method

Fingerprint Dive into the research topics of 'On the integrality gap of degree-4 sum of squares for planted clique'. Together they form a unique fingerprint.

  • Cite this

    Hopkins, S. B., Kothari, P., Henry Potechin, A., Raghavendra, P., & Schramm, T. (2018). On the integrality gap of degree-4 sum of squares for planted clique. ACM Transactions on Algorithms, 14(3), [28]. https://doi.org/10.1145/3178538