Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909894395822080 |
|---|---|
| author | Ding, Jian Du, Hang Li, Zhangsong |
| author_facet | Ding, Jian Du, Hang Li, Zhangsong |
| contents | Given two Erdős-Rényi graphs with $n$ vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation detection problem for the class of low-degree polynomial algorithms. We provide evidence that any degree-$O(ρ^{-1})$ polynomial algorithm fails for detection, where $ρ$ is the edge correlation. Furthermore, in the sparse regime where the edge density $q=n^{-1+o(1)}$, we provide evidence that any degree-$d$ polynomial algorithm fails for detection, as long as $\log d=o\big( \frac{\log n}{\log nq} \wedge \sqrt{\log n} \big)$ and the correlation $ρ<\sqrtα$ where $α\approx 0.338$ is the Otter's constant. Our result suggests that several state-of-the-art algorithms on correlation detection and exact matching recovery may be essentially the best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15931 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs Ding, Jian Du, Hang Li, Zhangsong Data Structures and Algorithms Probability Statistics Theory 68Q87, 62M20 Given two Erdős-Rényi graphs with $n$ vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation detection problem for the class of low-degree polynomial algorithms. We provide evidence that any degree-$O(ρ^{-1})$ polynomial algorithm fails for detection, where $ρ$ is the edge correlation. Furthermore, in the sparse regime where the edge density $q=n^{-1+o(1)}$, we provide evidence that any degree-$d$ polynomial algorithm fails for detection, as long as $\log d=o\big( \frac{\log n}{\log nq} \wedge \sqrt{\log n} \big)$ and the correlation $ρ<\sqrtα$ where $α\approx 0.338$ is the Otter's constant. Our result suggests that several state-of-the-art algorithms on correlation detection and exact matching recovery may be essentially the best possible. |
| title | Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs |
| topic | Data Structures and Algorithms Probability Statistics Theory 68Q87, 62M20 |
| url | https://arxiv.org/abs/2311.15931 |