Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912792327487488 |
|---|---|
| author | Li, Zhangsong |
| author_facet | Li, Zhangsong |
| contents | In this paper, assuming the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs $\mathcal G(n,q;ρ)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $ρ<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{DDL23+}; (2) the detection problem between a pair of correlated sparse stochastic block models $\mathcal S(n,\tfracλ{n};k,ε;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n};k,ε)$ when $ε^2 λs<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{CDGL24+}.
One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=Ω(1)$. This framework provides a useful tool for performing reductions between different inference tasks, without requiring a strengthened version of the low-degree conjecture as in \cite{MW23+, DHSS25+}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09832 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity Li, Zhangsong Machine Learning Data Structures and Algorithms Probability Statistics Theory 68Q87, 68Q17 In this paper, assuming the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs $\mathcal G(n,q;ρ)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $ρ<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{DDL23+}; (2) the detection problem between a pair of correlated sparse stochastic block models $\mathcal S(n,\tfracλ{n};k,ε;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n};k,ε)$ when $ε^2 λs<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrtα$ lies below the Otter's threshold, this resolves a remaining problem in \cite{CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=Ω(1)$. This framework provides a useful tool for performing reductions between different inference tasks, without requiring a strengthened version of the low-degree conjecture as in \cite{MW23+, DHSS25+}. |
| title | Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity |
| topic | Machine Learning Data Structures and Algorithms Probability Statistics Theory 68Q87, 68Q17 |
| url | https://arxiv.org/abs/2502.09832 |