Probability and Mathematical Physics Seminar

---

The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property

Speaker: Ilias Zadik, NYU Center for Data Science

Location: Warren Weaver Hall 1302

Date: Friday, February 21, 2020, 11:10 a.m.

Synopsis:

In this talk, we will focus on the planted clique model, denoted by G(n,1/2,k), which is originally introduced by Jerrum in 1992. An instance of G(n,1/2,k) is generated by planting a clique of size k uniformly at random in a vanilla Erdős-Rényi graph G(n,1/2). The inference goal is to recover the vertices of the planted clique from an instance of G(n,1/2,k). The study of the model have been the focus of a large line of work arising from the probability theory, computer science and statistics communities. While we know that as long as k > (2+\epsilon) log_2(n), for some \epsilon > 0, the clique is recoverable via brute-force methods, no polynomial-time method is proven to succeed unless k > c \sqrt{n} for some c > 0. A convincing explanation for the failure of polynomial-time methods in the regime where k is much smaller than \sqrt{n} is currently missing in the literature of the model.

We are going to discuss some new results on the geometry of the dense subgraphs in an instance of G(n,1/2,k). Our results suggest that k = Θ (\sqrt{n}) admits an explanation as the phase transition point for the presence of a certain Overlap Gap Property (OGP) on the space of dense subgraphs. OGP is a disconnectivity notion which originates in spin glass theory and is known to suggest algorithmic harness when it appears. Finally, we show that OGP implies the failure of a large family of MCMC methods to recover the clique when k is much smaller than \sqrt{n}.

This is joint work with David Gamarnik.