Cover Image

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation

Fuente: arXiv

Saved in:

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

Similar Items

Robust random graph matching in Gaussian models via vector approximate message passing
by: Li, Zhangsong
Published: (2024)

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

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

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

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

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

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

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)

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

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

Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
by: Chen, Guanyi, 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)

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)

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

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

Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
by: Muratori, Andrea, et al.
Published: (2024)

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)

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

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)

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

An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability
by: Vakhania, Nodari, et al.
Published: (2024)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
by: Chen, Shujing, 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)

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

A non-iterative polynomial algorithm for linear programming
by: Jing-Yuan, Wei
Published: (2013)

Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity
by: Chen, Zongchen, et al.
Published: (2022)

Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories
by: Friedl, Katalin, et al.
Published: (2025)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
by: Jaquard, Hugo, et al.
Published: (2024)

Finding planted cliques using gradient descent
by: Gheissari, Reza, et al.
Published: (2023)