2022/12/11 by Rares-Darius Buhai, Buhai, Rares-Darius, Pravesh K. Kothari +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2212.05619
openalex publication_date 2022/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian 2001. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices (Mehta, Mckenzie, Trevisan 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching n1/2 -- the information-theoretic threshold in the semi-random model (Steinhardt 2017) and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige 2019 and Steinhardt 2017. 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(n2/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.