Cover Image

Robust random graph matching in Gaussian models via vector approximate message passing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Li, Zhangsong
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Data Structures and Algorithms Probability Statistics Theory 68Q87, 90C35
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
by: Ding, Jian, et al.
Published: (2023)

A Smooth Computational Transition in Tensor PCA
by: Li, Zhangsong
Published: (2025)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
by: Li, Zhangsong
Published: (2025)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
by: Gong, Shuyang, et al.
Published: (2024)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
by: Ding, Jian, et al.
Published: (2023)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
by: Chen, Guanyi, et al.
Published: (2024)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

The Algorithmic Phase Transition in Correlated Spiked Models
by: Li, Zhangsong
Published: (2025)

Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
by: Gong, Shuyang, et al.
Published: (2026)

A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
by: Ding, Jian, et al.
Published: (2022)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
by: Göbel, Andreas, et al.
Published: (2025)

Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
by: Cheairi, Houssam El, et al.
Published: (2024)

The Kikuchi Hierarchy and Tensor PCA
by: Wein, Alexander S., et al.
Published: (2019)

Private Evolution Converges
by: González, Tomás, et al.
Published: (2025)

Efficiently matching random inhomogeneous graphs via degree profiles
by: Ding, Jian, et al.
Published: (2023)

Computing the probability of intersection
by: Barvinok, Alexander
Published: (2025)

Easy, robust approximate message passing for planted spike models
by: Ivkov, Misha, et al.
Published: (2026)

Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
by: Chen, Guanyi, et al.
Published: (2025)

Balanced connected partitions of edge-weighted graphs: Hardness and solving methods
by: Davari, Morteza, et al.
Published: (2025)

Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
by: Fan, Zhou, et al.
Published: (2026)

Benign landscapes for synchronization on spheres via normalized Laplacian matrices
by: McRae, Andrew D.
Published: (2025)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
by: Goerigk, Marc, et al.
Published: (2026)

Robust Graph-Based Semi-Supervised Learning via $p$-Conductances
by: Robertson, Sawyer Jack, et al.
Published: (2025)

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
by: Schwardt, J., et al.
Published: (2025)

Optimal rolling of fair dice using fair coins
by: Huber, Mark, et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Adversarially-Robust Inference on Trees via Belief Propagation
by: Hopkins, Samuel B., et al.
Published: (2024)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
by: Davies, Ewan, et al.
Published: (2026)

Correlation detection in trees for planted graph alignment
by: Ganassali, Luca, et al.
Published: (2021)

Learning Mixtures of Gaussians Using Diffusion Models
by: Gatmiry, Khashayar, et al.
Published: (2024)

Universality of first-order methods on random and deterministic matrices
by: Gorini, Nicola, et al.
Published: (2026)

Fitting an ellipsoid to a quadratic number of random points
by: Bandeira, Afonso S., et al.
Published: (2023)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

Sharp threshold for network recovery from voter model dynamics
by: Du, Hang, et al.
Published: (2025)

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
by: Du, Hang, et al.
Published: (2025)

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
by: Göbel, Andreas, et al.
Published: (2026)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
by: Chen, Shujing, et al.
Published: (2025)