Low-degree phase transitions for detecting a planted clique in sublinear time

We consider the problem of detecting a planted clique of size k in a random graph on n vertices. When the size of the clique exceeds (n), polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear time -- algorithms in the high-signal regime when k = (n^1/2 +), for some > 0. To this end, we consider algorithms that non-adaptively query a subset M of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of non-adaptive low-degree algorithms: under the scaling M = (n^), the clique can be detected when > 3 (1/2 -) but not when < 3 (1/2 -). As a result, the best known runtime for detecting a planted clique, O (n^3 (1/2-) ), cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound -- based on bounding the conditional low-degree likelihood ratio -- reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for every non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective.