The algorithmic phase transition of random graph alignment problem

DOI10.1007/S00440-025-01370-ZMaRDI QIDQ6988566zbMATH OpenFDO

Authors Hang Du, Shuyang Gong, Rundong Huang

Publication date 4 May 2025

Published in Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00440-025-01370-Z

zbMATH Keywords

computational hardnessefficient algorithmphase transitionrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Correlation detection in trees for planted graph alignment
• Detection threshold for correlated Erdős-Rényi graphs via densest subgraph
• Disordered systems insights on computational hardness
• Distribution inequalities for the binomial law
• Efficient random graph matching via degree profiles
• Exact matching of random graphs with constant correlation
• Finding a large submatrix of a Gaussian random matrix
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• Matching recovery threshold for correlated random graphs
• Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Optimal low-degree hardness of maximum independent set
• Optimization of the Sherrington-Kirkpatrick Hamiltonian
• Partial Recovery in the Graph Alignment Problem
• Random graph matching at Otter's threshold via counting chandeliers
• Seeded graph matching for correlated Erdős-Rényi graphs
• Seeded graph matching via large neighborhood statistics
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Statistical limits of correlation detection in trees
• Testing correlation of unlabeled random graphs
• Testing network correlation efficiently via counting trees
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• The probabilistic method
• The quadratic assignment problem. Theory and algorithms
• Tight Lipschitz hardness for optimizing mean field spin glasses

Cited in

(3)

• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Efficiently matching random inhomogeneous graphs via degree profiles
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties

This page was built for publication: The algorithmic phase transition of random graph alignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988566)