15 papers
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…
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…
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…
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…
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…