10 Lectures and 42 Open Problems — The planted clique problem

Definitions and mathematical statement

On the labelled vertex set $[n]=\{1,\ldots,n\}$, first include each unordered pair independently with probability $1/2$. Independently choose a uniformly random set $S\subseteq[n]$ of size $k$ and add all missing edges within $S$. Denote the resulting distribution by $\mathcal G_{n,k}$; the null distribution $\mathcal G_{n,0}$ has no planted set.

The recovery problem asks an algorithm to output the planted clique, or equivalently the maximum clique in the source's regime $k\gg\log n$. The detection problem asks it to distinguish these two graph distributions. Success with high probability means probability $1-o(1)$ as $n\to\infty$, including graph and algorithm randomness; for detection, this requirement applies under both hypotheses.

Can either task be solved in time polynomial in $n$ when \[ k=\left\lfloor\frac{\sqrt n}{\log n}\right\rfloor, \] or more generally in a nontrivial regime $\log n\ll k\ll\sqrt n$? The polynomial exponent must be independent of $n$.

The source also asks whether recovery is possible in quasi-linear time in the dense input size, namely $n^2(\log n)^{O(1)}$, below the threshold $k=(1/\sqrt e-\varepsilon)\sqrt n$ for some fixed $0<\varepsilon<1/\sqrt e$. Finding a large clique in an arbitrary graph is a different worst-case problem. Here the entire promise is the specified random construction; the algorithm is not given $S$.

Short English statement

Can planted cliques below the square-root scale be detected or recovered in polynomial time, or recovered below the stated threshold in quasi-linear dense-input time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2800203 (AMR-027-0203), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Bandeira - 42 Open Problems in Data Science (2016), Open Problem 2.3. Original source indexed by AMR-027-0203. https://afonsobandeira.wordpress.com/2015/09/30/10l42pgraphs/.
• S3 A. S. Bandeira, Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science, corresponding numbered problem and surrounding definitions. https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf.