Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
From MaRDI portal
Publication:6072327
DOI10.1007/s10208-022-09575-7zbMath1522.90092arXiv1907.08883OpenAlexW4282555249MaRDI QIDQ6072327
Cheng Mao, Zhou Fan, Jiaming Xu, Yihong Wu
Publication date: 13 October 2023
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.08883
Convex programming (90C25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis ⋮ Matching recovery threshold for correlated random graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
- The local semicircle law for a general class of random matrices
- Hanson-Wright inequality and sub-Gaussian concentration
- Bulk universality for generalized Wigner matrices
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- On convex relaxation of graph isomorphism
- Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
- On the free convolution with a semi-circular distribution
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
This page was built for publication: Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality