Counting Stars Is Constant-Degree Optimal for Detecting Any Planted Subgraph: Extended Abstract
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.
Cite
Text
Yu et al. "Counting Stars Is Constant-Degree Optimal for Detecting Any Planted Subgraph: Extended Abstract." Conference on Learning Theory, 2024.Markdown
[Yu et al. "Counting Stars Is Constant-Degree Optimal for Detecting Any Planted Subgraph: Extended Abstract." Conference on Learning Theory, 2024.](https://mlanthology.org/colt/2024/yu2024colt-counting/)BibTeX
@inproceedings{yu2024colt-counting,
title = {{Counting Stars Is Constant-Degree Optimal for Detecting Any Planted Subgraph: Extended Abstract}},
author = {Yu, Xifan and Zadik, Ilias and Zhang, Peiyuan},
booktitle = {Conference on Learning Theory},
year = {2024},
pages = {5163-5165},
volume = {247},
url = {https://mlanthology.org/colt/2024/yu2024colt-counting/}
}