TY - JOUR
T1 - On the integrality gap of degree-4 sum of squares for planted clique
AU - Hopkins, Samuel B.
AU - Kothari, Pravesh
AU - Henry Potechin, Aaron
AU - Raghavendra, Prasad
AU - Schramm, Tselil
N1 - Funding Information:
This article contains statements of results and a high-level overview of the techniques used to prove a nearly tight integrality gap for degree-4 Sum of Squares for planted clique. For further details, we refer the reader to either of the following: (1) Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program, Prasad Raghavendra and Tselil Schramm [52], which contains a succinct proof of the degree-4 integrality gap. (2) SoS and Planted Clique: Tight Analysis of MPW Moments at All Degrees and an Optimal Lower Bound at Degree Four, Samuel B. Hopkins, Pravesh K. Kothari, and Aaron Potechin [39], which situates the degree-4 integrality gap in a general framework, allowing in addition a tight analysis of the degree-d integrality gap construction introduced in References [2, 25]. S.B.H., P.K., and A.P. did some of the work represented in this article as interns at Microsoft Research New England. S.B.H. acknowledges support from an NSF Graduate Research Fellowship under grant no. 1144153. A.P. acknowledges support from an NSF Graduate Research Fellowship under grant no. 0645960. P.R. acknowledges support from an NSF Career Award, NSF CCF-1407779, and the Alfred. P. Sloan Fellowship. T.S. acknowledges support from an NSF Graduate Research Fellowship under grant no. 1106400. Authors’ addresses: S. B. Hopkins, Cornell University, 107 Hoy Road, Ithaca, NY 14853-7501; email: samhop@cs.cornell.edu; P. Kothari, Princeton University, 35 Olden Street, Princeton, NJ 08540-5233; email: kothari@cs.utexas.edu; A. H. Potechin, The University of Chicago, 1100 East 58th Street, Chicago, IL 60637; email: aaronpotechin@gmail.com; P. Raghavendra, University of California, Berkeley, 253 Cory Hall, Berkeley, CA 94720-1770; email: prasad@cs.berkeley.edu; T. Schramm, Harvard John A. Paulson School of Engineering and Applied Sciences, Pierce Hall, 29 Oxford Street, Cambridge, MA 02138; email: tschramm@cs.berkeley.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2018 ACM 1549-6325/2018/06-ART28 $15.00 https://doi.org/10.1145/3178538
PY - 2018/7
Y1 - 2018/7
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 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].
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 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].
KW - Planted clique
KW - Random matrices
KW - Sum of Squares method
UR - http://www.scopus.com/inward/record.url?scp=85052591350&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052591350&partnerID=8YFLogxK
U2 - 10.1145/3178538
DO - 10.1145/3178538
M3 - Article
AN - SCOPUS:85052591350
SN - 1549-6325
VL - 14
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 28
ER -