Detection-Recovery Gap for Planted Dense Cycles

Cheng Mao, Alexander S. Wein, Shenduo Zhang
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2440-2481, 2023.

Abstract

Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n \tau$ and edge density $p$ is planted in an Erdős–Rényi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if $n^{-3/4} \ll \tau \ll n^{-1/2}$ and $p = C q = \Theta(1)$ for a constant $C>1$, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-mao23a, title = {Detection-Recovery Gap for Planted Dense Cycles}, author = {Mao, Cheng and Wein, Alexander S. and Zhang, Shenduo}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {2440--2481}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/mao23a/mao23a.pdf}, url = {https://proceedings.mlr.press/v195/mao23a.html}, abstract = {Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n \tau$ and edge density $p$ is planted in an Erdős–Rényi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if $n^{-3/4} \ll \tau \ll n^{-1/2}$ and $p = C q = \Theta(1)$ for a constant $C>1$, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.} }
Endnote
%0 Conference Paper %T Detection-Recovery Gap for Planted Dense Cycles %A Cheng Mao %A Alexander S. Wein %A Shenduo Zhang %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-mao23a %I PMLR %P 2440--2481 %U https://proceedings.mlr.press/v195/mao23a.html %V 195 %X Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n \tau$ and edge density $p$ is planted in an Erdős–Rényi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if $n^{-3/4} \ll \tau \ll n^{-1/2}$ and $p = C q = \Theta(1)$ for a constant $C>1$, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.
APA
Mao, C., Wein, A.S. & Zhang, S.. (2023). Detection-Recovery Gap for Planted Dense Cycles. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:2440-2481 Available from https://proceedings.mlr.press/v195/mao23a.html.

Related Material