Algorithms Approaching the Threshold for Semi-random Planted Clique

We design new polynomial-time algorithms for recovering planted cliques in the semirandom graph model introduced by Feige and Kilian [FK01]. The previous best algorithms for this model succeed if the planted clique has size at least 2/3 in a graph with vertices [MMT20, CSV17]. Our algorithms work for planted-clique sizes approaching 1/2the information-theoretic threshold in the semi-random model [Ste17] and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige [Fei19] and Steinhardt [Ste17]. To generate a graph in the semi-random planted-clique model, we first 1) plant a clique of size in an -vertex Erdős-Rényi 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 (1/ ) -time algorithm that recovers a clique of size in this model whenever ≥ 1/2+ . In fact, our algorithm computes, with high probability, a list of about / cliques of size that contains the planted clique. Our algorithms also extend to arbitrary edge probabilities and improve on the previous best guarantee whenever ≤ 1 --0.001 . Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite Erdős-Rényi 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 2/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.