In their seminal paper of 1998 Alon, Krivelevich and Sudakov have established that a clique imbedded into a random graph can be recovered using a polynomial time (spectral) method when its size is at least the square root of the size of the graph. Repeated failed attempts to break this square root barrier raised the possibility that the problem is algorithmically hard below the square root regime, but this unfortunately still remains only a conjecture. The question gained prominence not only in the field of random graphs, but also in the fields of theoretical computer science and the high-dimensional statistics, earning the status of the ”mother” of many possibly average-case hard inference problems.

As an attempt to explain the conjectured hardness below the square root threshold, and inspired by insights from the field of spin glasses, we study the solution space geometry of the hidden clique problem, both below and above the conjecturally hard threshold. Specifically, we consider the densest subgraph problem as a function of an intersection size with the planted clique. Based on the first moment approximation, we prove that the model exhibits a certain monotonicity phase transition around the conjectured hardness threshold, and for certain parameter choices exhibits the Overlap Gap Property (OGP): every sufficiently dense subgraph either contains a substantial fraction of the hidden clique or has almost no intersection with it. The evidence of OGP thus obtained is then rigorously verified using the second moment method, albeit only in the case when the hidden clique size is a small power of the graph size.

Joint work with Ilias Zadik (MIT/NYU).