[edit]
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5163-5165, 2024.
Abstract
We prove that whenever p=Ω(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.