Book ; Online: Low-Degree Hardness of Detection for Correlated Erd\H{o}s-R\'enyi Graphs
2023
Abstract: Given two Erd\H{o}s-R\'enyi graphs with $n$ vertices whose edges are correlated through a latent ...
| Abstract | Given two Erd\H{o}s-R\'enyi 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(\rho^{-1})$ polynomial algorithm fails for detection, where $\rho$ 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 $\rho<\sqrt{\alpha}$ where $\alpha\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. Comment: 40 pages |
|---|---|
| Keywords | Computer Science - Data Structures and Algorithms ; Mathematics - Probability ; Mathematics - Statistics Theory ; 68Q87 ; 62M20 |
| Subject code | 511 |
| Publishing date | 2023-11-27 |
| Publishing country | us |
| Document type | Book ; Online |
| Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.