Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract

摘要

We prove that whenever $p=\Omega(1)$ and for any graph $H$, counting $O(1)$-stars is optimal among all constant degree polynomial tests in terms of strongly separating an instance of $G(n,p),$ from the union of a random copy of $H$ with an instance of $G(n,p).$ Our work generalizes and extends multiple previous results on the inference abilities of $O(1)$-degree polynomials in the literature.