Low-degree phase transitions for detecting a planted clique in sublinear time
<|reference_start|>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 $\Theta(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear time -- algorithms in the high-signal regime when $k = \Theta(n^{1/2 + \delta})$, for some $\delta > 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 $\lvert M \rvert = \Theta(n^{\gamma})$, the clique can be detected when $\gamma > 3(1/2 - \delta)$ but not when $\gamma < 3(1/2 - \delta)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-\delta)})$, 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.<|reference_end|>
@article{mardia2024low-degree,
    title={Low-degree phase transitions for detecting a planted clique in sublinear
  time},
    author={Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein},
    journal={arXiv preprint arXiv:2402.05451},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05451},
    primaryClass={cs.DS cs.CC stat.ML}
}