Matching Correlated Random Geometric Graphs @SimonsInstitute
Matching Correlated Random Geometric Graphs  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 2 days ago
Shuangping Li (Yale University)
https://simons.berkeley.edu/talks/shuangping-li-yale-university-2026-10-15
Probabilistic Phenomena on Graphs, Groups, and Manifolds

We study graph matching for two correlated random geometric graphs whose vertex labels have been permuted. The graphs are generated from correlated latent points on the high-dimensional sphere, with edges determined by thresholded inner products. We give a polynomial time algorithm that can achieve exact recovery of the hidden matching for any fixed positive correlation. We also characterize the information-theoretic threshold for exact recovery, up to constant factors, over a broad range of dimensions.

This is based on joint work with Dong Huang, Ankang Jiao, and Zhangsong Li.
Matching Correlated Random Geometric GraphsFault-Tolerant Quantum Computation with Adversarial ErrorsApollonian random manifolds and their bass notesSampling from the Sherrington-Kirkpatrick model up to β<1/2Coboundary Expansion and Locally Testable Codes (Part 2)The BRRY analysis of the INW generator is optimalTalk by Hsin-Yuan Huang (Oratomic, Caltech)Strong Spatial Mixing for Colorings on Trees and its Algorithmic ApplicationsSpectral gap of 1D quantum Gibbs samplersSharp Bounds on Ground State Energy of the SYK ModelRare event analysis via stochastic optimal controlThe Pseudorandomness Toolkit (Part 2)
Simons Institute for the Theory of Computing |

Matching Correlated Random Geometric Graphs

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER