Detection of local geometry in random graphs: information-theoretic and computational limits
arXiv:2603.24545v1 Announce Type: cross
Abstract: We study the problem of detecting local geometry in random graphs. We introduce a model $\mathcal{G}(n, p, d, k)$, where a hidden community of average size $k$ has edges drawn as a random geometric gra…