Algorithms Approaching the Threshold for Semi-random Planted Clique

Rares Darius Buhai, Pravesh K. Kothari, David Steurer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n1/2-the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. To generate a graph in the semi-random planted-clique model, we first 1) plant a clique of size k in an n-vertex-graph with edge probability 1/2 and then adversarially add or delete an arbitrary number edges not touching the planted clique and delete any subset of edges going out of the planted clique. For every ">0, we give an nO(1/")-time algorithm that recovers a clique of size k in this model whenever k ≥ n1/2+". In fact, our algorithm computes, with high probability, a list of about n/k cliques of size k that contains the planted clique. Our algorithms also extend to arbitrary edge probabilities p and improve on the previous best guarantee whenever p ≤ 1-n-0.001. Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite-random graphs into algorithms for semi-random planted clique. Analogous to the (conjecturally) optimal algorithms for the fully-random model, the previous best guarantees for semi-random planted clique correspond to spectral relaxations of biclique numbers based on eigenvalues of adjacency matrices. We construct an SDP lower bound that shows that the n2/3 threshold in prior works is an inherent limitation of these spectral relaxations. We go beyond this limitation by using higher-order sum-of-squares relaxations for biclique numbers. We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree polynomial model.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages1918-1926
Number of pages9
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Externally publishedYes
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • planted clique
  • semi-random
  • semidefinite programming
  • sum-of-squares hierarchy

Fingerprint

Dive into the research topics of 'Algorithms Approaching the Threshold for Semi-random Planted Clique'. Together they form a unique fingerprint.

Cite this