3 citations · 4 across the 14 of their papers we have counts for
7 papers · 1 filter
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…