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: Chapter in Book/Report/Conference proceedingConference contribution

9 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 Erdos-Renyi 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 [MPW15] and Deshpande and Montanari [DM15bJ. Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless υ √n Polylogn, improving upon the bound w ≫ n1/3 due to [DM 15b]. 2. For 2 < d = o(√log{n)), degree 2d SoS does not recover the planted clique unless υ Ggt; n1/(d+i)/(2dpolylogn), improving upon the bound due to [MPW15]. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works [MPW15, DM15b, FK03] by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev [GriOla].

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1079-1095
Number of pages17
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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., Potechin, A. H., Raghavendra, P., & Schramm, T. (2016). On the integrality gap of degree-4 sum of squares for planted clique. In R. Krauthgamer (Ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (pp. 1079-1095). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974331.ch76