In this talk, I will present a new polynomial time algorithm for recovering planted cliques in the semi-random graph model of Feige and Kilian from 2001. In the Feige-Kilian model, a graph G on vertex set V is chosen by a combination of benign random and adaptive "adversarial" choices and can be thought of as a "robust" counterpart of the well-studied "fully-random" planted clique problem:
1) choose a planted clique on a set of k vertices S,
2) "benign random choice": include each edge between S and V\S independently at random,
3) "adaptive worst-case choice": deleting any set of edges between S and V\S and adding any set of edges with both endpoints in V\S.
The previous best algorithms for this model succeed if the planted clique has a size of at least n^{2/3} in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n^{1/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 an open question of Feige (2019) and Steinhardt (2017). Our algorithm is based on high constant degree sum-of-squares relaxation of the clique SDP and the analysis relies on a new connection between finding planted cliques and efficient certificates of upper bounds on clique number of unbalanced bicliques in bipartite random graphs.
Based on joint work with Rares Buhai and David Steurer.
Copyright. All Rights Reserved.