# Polynomial-time distinguishability threshold of planted clique

I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(n,\frac{1}{2})$ of Erdos Renyi Random graphs from $G_k(n,\frac{1}{2})$ -- the distribution of graphs formed by planting a clique of size $k$ in $G(n,\frac{1}{2})$. This problem (as well as its natural bipartite variant) is conjectured hard for $k=n^{\frac{1}{2} - \delta}$ when $\delta >0$ is an absolute constant. In this post, you can think of $k=n^{\frac{1}{4}}$.

It is often assumed as a hardness assumption that no polynomial time algorithm can distinguish $G(n,\frac{1}{2})$ from $G_k(n,\frac{1}{2})$ with "non-negligible" advantage. Formally, this means that for any "non-negligible" advantage $\epsilon>0$, there is no polynomial time algorithm $f$ from graphs to $\{0,1\}$ such that $|\Pr[ f(G)=1 ] - \Pr[f(G_k)=1] | > \epsilon$ for $G \sim G(n,\frac{1}{2})$ and $G_k \sim G_k(n,\frac{1}{2})$.

In applications of this hardness assumption which I have seen, "non-negligible" is often taken to mean an absolute constant. In other words, it is believed that no polynomial-time algorithm can distinguish between the two distributions with constant advantage. My question is whether this extends to sub-constant $\epsilon$ which are not too small? i.e., is it believed hard to distinguish the two distributions with advantage, say, $\epsilon = \frac{1}{n}$ or $\epsilon = \frac{1}{\sqrt{n}}$ ? Clearly, there is some advantage $\epsilon$ more than exponentially small in $n$ but less than a constant where this problem crosses from being easy to being hard, and I'm interested in what is known about this "threshold".

The only reference to sub-constant distinguishability I could find is in this paper, which (assuming I understand the paper correctly) seems to rule out polynomial-time distinguishability with $\epsilon > \frac{1}{o(n)}$ via "statistical algorithms." Anybody know what else is known / believed?

• I am a bit confused about what you're asking. It is known that the largest clique in a random graph will w.h.p. be $2lgn$ or $2lgn+1$, so any plant that's larger than that can, in principle, be detected, though probably not by a polynomial time algorithm. – Lev Reyzin Mar 19 '14 at 21:46
• I'm referring to polynomial time distinguishability. – sd234 Mar 19 '14 at 21:54
• a somewhat trivial comment: if your algorithm can draw as many samples as it wants from the two distributions, then by standard arguments an algorithm with advantage $\epsilon$ for a single sample translates to an algorithm that takes $O(\epsilon^{-2})$ samples and has constant advantage. – Sasho Nikolov Mar 20 '14 at 3:55

My understanding is that no algorithm is known for finding cliques with polynomially high success probability for $k=O(n^{1/2-\epsilon})$. I think it is believed that getting a polynomially large success probability is not possible.