Polynomial-time distinguishability threshold of planted clique

Question

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?

Answer 1

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.

The reason for my holding this belief is that after a clique-finding algorithm outputs a clique, one can check if it succeeded. So if the algorithm fails, it can be re-run until the clique is found, which would yield polynomial time algorithm for polynomially high edges. Of course, this isn't quite right -- an algorithm may be deterministic and its success could depend on the random target graph, and so this trick wouldn't work. So this is more intuition than proof.

The paper of mine you cite gives concrete lower bounds, but only for a restricted class of algorithms.