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 = Θ(n1/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(n3(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.