Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
<|reference_start|>Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task between a ``null'' Erd\H{o}s-R\'{e}nyi random graph G(n,p) and a ``planted'' random graph which is the union of G(n,p) together with a random copy of H=H_n. Our notion of planted model is a generalization of a plethora of recently studied models initiated with the study of the planted clique model (Jerrum 1992), which corresponds to the special case where H is a k-clique and p=1/2.   Over the last decade, several papers have studied the power of low-degree polynomials for limited choices of H's in the above task. In this work, we adopt a unifying perspective and characterize the power of \emph{constant degree} polynomials for the detection task, when \emph{H=H_n is any arbitrary graph} and for \emph{any p=\Omega(1).} Perhaps surprisingly, we prove that the optimal constant degree polynomial is always given by simply \emph{counting stars} in the input random graph. As a direct corollary, we conclude that the class of constant-degree polynomials is only able to ``sense'' the degree distribution of the planted graph H, and no other graph theoretic property of it.<|reference_end|>
@article{yu2024counting,
    title={Counting Stars is Constant-Degree Optimal For Detecting Any Planted
  Subgraph},
    author={Xifan Yu, Ilias Zadik, Peiyuan Zhang},
    journal={arXiv preprint arXiv:2403.17766},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.17766},
    primaryClass={math.ST cs.CC cs.DS stat.TH}
}