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

Xifan Yu, Ilias Zadik, Peiyuan Zhang
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5163-5165, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v247-yu24a, title = {Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract}, author = {Yu, Xifan and Zadik, Ilias and Zhang, Peiyuan}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {5163--5165}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/yu24a/yu24a.pdf}, url = {https://proceedings.mlr.press/v247/yu24a.html}, 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.} }
Endnote
%0 Conference Paper %T Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract %A Xifan Yu %A Ilias Zadik %A Peiyuan Zhang %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-yu24a %I PMLR %P 5163--5165 %U https://proceedings.mlr.press/v247/yu24a.html %V 247 %X 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.
APA
Yu, X., Zadik, I. & Zhang, P.. (2024). Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph: Extended Abstract. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:5163-5165 Available from https://proceedings.mlr.press/v247/yu24a.html.

Related Material