TY - GEN

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

AU - Hopkins, Samuel B.

AU - Kothari, Pravesh

AU - Potechin, Aaron Henry

AU - Raghavendra, Prasad

AU - Schramm, Tselil

PY - 2016

Y1 - 2016

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84963713726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963713726&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch76

DO - 10.1137/1.9781611974331.ch76

M3 - Conference contribution

AN - SCOPUS:84963713726

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1079

EP - 1095

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -