Algorithms approaching the threshold for semi-random planted clique
share
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian <cit.>. The previous best algorithms for this model succeed if the planted clique has size at least n^2/3 in a graph with n vertices (Mehta, Mckenzie, Trevisan, 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching n^1/2 – the information-theoretic threshold in the semi-random model <cit.> and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. Our algorithms are based on higher constant degree sum-of-squares relaxation and 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. The use of a higher-constant degree sum-of-squares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size k =o(n^2/3). 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-polynomials model.
READ FULL TEXT