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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Lev Reyzin
    Mar 19, 2014 at 21:46
  • $\begingroup$ I'm referring to polynomial time distinguishability. $\endgroup$
    – sd234
    Mar 19, 2014 at 21:54
  • $\begingroup$ 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. $\endgroup$ Mar 20, 2014 at 3:55

1 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.

  • $\begingroup$ Thanks Lev. Three questions: 1- You said it is believed that no algorithm finds a hidden clique with polynomially high success probability. Do you think the same holds for the (possibly easier) problem of distinguishing the two distributions? I.e. outputing 1 with 1/poly greater probability for one distribution than for the other. 2- Can you think of any references which assume 1/poly(n) hardness of the search problem or the distinguishing problem? 3- Does the lowerbound in your paper for statistical algorithms hold for the distinguishing problem as well, or only for the search problem? $\endgroup$
    – sd234
    Mar 20, 2014 at 2:20
  • $\begingroup$ 1) yes, I think so but have no citations. The closest reason I have is that this is known to be the case for learning parity with noise, which has certain connections to planted clique, 2) I don't know of any, 3) Yes, the proof should go through for distinguishing graphs with plants from random graphs because the uniform distribution is the "reference distribution" in our application of statistical dimension. It may take reading the paper to understand what this means. $\endgroup$
    – Lev Reyzin
    Mar 20, 2014 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.