IFML Seminar: 03/13/25 - Near-Optimal Algorithms for Semirandom Planted Clique

Abstract:
I will present a polynomial time algorithm to recover planted cliques in the semi random models introduced by Feige and Kilian (1998) and a variant by Steinhardt (2017).
 

In the Steinhardt model, the input graph is obtained by planting a clique and arbitrarily and adaptively corrupting edges that do not touch the vertices in the clique. In the Feige-Kilian model, a monotone adversary can arbitrarily and adaptively delete any subset of edges in the cut defined by the vertices of the planted clique (monotone adversary). The previous best algorithms for both these models require that the planted clique be of size at least n^{2/3} in a graph with n vertices. 

 

In the Feige-Klilian model, we give an algorithm that succeeds in recovering planted cliques of size n^{1/2+\epsilon} for any $\epsilon>0$ in time $n^{O(1/\epsilon)}$. This almost resolves in the affirmative, an open question of Feige, who asked whether recovering planted cliques in the semirandom model could be done at the same thresholds as the best-known results for the well-studied (entirely random, and thus substantially easier) planted clique problem. 

 

In the variant without the monotone adversary introduced by Steinhardt (2017), our algorithm succeeds if the clique size is $\geq O(\sqrt{n \log^{3} n)$. The analysis of our algorithm was improved to show that it succeeds at clique size $\geq O(\sqrt{n log n})$ by Guruswami and Po-Wang. This matches the best-known clique size threshold for fully random planted clique within a $\sqrt{\log n}$ factor and resolves an open question of Steinhardt. 

 

Based on joint works with Jaroslaw Blasiok (ETH Zurich), Rares Buhai (ETH Zurich), and David Steurer (ETH Zurich).