3 citations · 4 across the 14 of their papers we have counts for
18 papers
Graph Matching in Random Geometric Graphs I: Efficient Algorithms
Dong Huang, Ankang Jiao, Shuangping Li +1
We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from latent unit vectors in $\mathbb R^d…
Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
Zhangsong Li
We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \[ \boldsymbol{Y}=\frac{1}{\sqrt{n}} \…
The Conclave Process
Itai Benjamini, Zhenhao Cai, Guanyi Chen +2
We introduce a stochastic model for the papal conclave in which cardinals vote repeatedly among themselves until one cardinal receives all the votes. In each round, the probabi…
On Injectivity of Phase Retrieval
Zhangsong Li
In this short note, we prove that if with has i.i.d.\ standard complex Gaussian entries, then the probability that the phase retrieval map g…
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
Zhangsong Li
The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, t…
Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
Shuyang Gong, Dong Huang, Zhangsong Li
We consider the problem of community detection from the joint observation of a high-dimensional covariate matrix and sparse networks, all encoding noisy, partial information ab…
Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
Zhangsong Li
We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple…
The Algorithmic Phase Transition in Correlated Spiked Models
Zhangsong Li
We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices $$ X=\tfracλ{\sqrt{n}} xu^{\top}+W, \quad Y=\tfracμ{\sqrt{n}} yv^{\top}+…
A Smooth Computational Transition in Tensor PCA
Zhangsong Li
We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order- tensor PCA problem where is a fixed integ…
Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection
Shuyang Gong, Zhangsong Li, Qiheng Xu
For a -uniform random hypergraph on vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is , the projection of such a…
Asymptotic diameter of preferential attachment model
Hang Du, Shuyang Gong, Zhangsong Li +1
We study the asymptotic diameter of the preferential attachment model with parameters and . Building on the recent work \cite{VZ25},…
A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials
Zhangsong Li
In this paper, we study the problem of multivariate shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a laten…
Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
Guanyi Chen, Jian Ding, Shuyang Gong +1
Consider a pair of sparse correlated stochastic block models subsampled from a common parent stochastic block model with two symmetric communities, a…
Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
Zhangsong Li
In this paper, assuming the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correla…
Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
Zhangsong Li
In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested i…
A computational transition for detecting correlated stochastic block models by low-degree polynomials
Guanyi Chen, Jian Ding, Shuyang Gong +1
Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consi…
The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
Shuyang Gong, Zhangsong Li
Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permuta…
Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
Jian Ding, Hang Du, Zhangsong Li
Given two Erdős-Rényi graphs with vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation de…