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