Open Source
Sharp detection thresholds for random geometric graphs with polynomial average degrees
arXiv stat.TH0 views
arXiv:2610.08517v1 Announce Type: cross Abstract: We study the random geometric graph formed by connecting $n$ independent uniform points on $\mathbb S^{d-1}$ whenever their inner product exceeds a threshold chosen to give edge density $p$. We establish the conjectured dimensionality threshold for indistinguishability from the Erd\"{o}s-R\'enyi graph $G(n,p)$ throughout the sparse regime with polynomially growing average degree. Specifically, for every fixed $\delta>0$, if $p\to0$, $p\ge n^{-1+\delta}$, and $d\gg (np\log(1/p))^3$, then the Kullback-Leibler (KL) divergence between the two distributions vanishes. Our proof builds on the posterior analysis framework introduced in previous work of the authors, combining a truncated second moment analysis with Fourier and spherical harmonic expansions. As in prior works, we reduce the KL bound to controlling a truncated $\chi^2$-divergence $\Delta$ for the neighborhood of the last vertex conditional on the graph induced by the preceding vertices. We then bound $\Delta$ using a Fourier expansion of the conditional likelihood ratio for this neighborhood, where the high-frequency contribution is made negligible by truncation to a typical-degree event, while a spherical harmonic expansion approximates the low-frequency contribution in terms of posterior moments of bounded-degree harmonic polynomials. The key observation is that these moments and $\Delta$ satisfy a coupled system of cavity recurrences, yielding a self-bounding inequality that implies the desired KL bound.
Source:https://arxiv.org/abs/2610.08517PreviousWhere Do Two Populations of Persistence Diagrams Differ? Calibrated Local Inference at a Fixed BudgetNextEstimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade
Related posts
Astra can read and write weights to improve Qwen
0Hacker News
Distillation didn't help our small model until we took the labels away
0dev.to Machine Learning

462. Minimum Moves to Equal Array Elements II
0dev.to PHP
MUSBRIC: LEGO-Compatible Pneumatic Muscle Bricks for Reconfigurable Musculoskeletal Robots
0arXiv cs.RO
OpenFlyV2: An onboard vision-language-action model for aerial perception and navigation
0arXiv cs.RO
Show HN: Open Bot Avatars – a spec and renderer for interactive bot avatars
0Hacker News New