Zhangsong Li
Hello! I am a third-year Ph.D student in School of Mathematical Sciences at Peking University, where I am fortunate to be advised by Jian Ding. Previously, I obtained my B.S. degree in mathematics from Peking University.
My research interest lies in the intersection of probability, statistical inference and theoretical computer science.
Links: CV (last update: April 2026), arXiv preprint, Google Scholar.
Email: ramblerlzs at pku dot edu dot cn.
Research
- Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
Zhangsong Li
[arXiv]
- Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
Shuyang Gong, Dong Huang, Zhangsong Li
[arXiv]
- Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
Zhangsong Li
[arXiv]
- The Algorithmic Phase Transition in Correlated Spiked Models
Zhangsong Li
[arXiv] [Slides]
- Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter’s Threshold in the Entire Supercritical Regime
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
[arXiv]
- A Smooth Computational Transition in Tensor PCA
Zhangsong Li
[arXiv]
- Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection
Shuyang Gong, Zhangsong Li, Qiheng Xu
Conference version to appear in ISIT 2026.
[arXiv]
- Asymptotic Diameter of Preferential Attachment Model
Hang Du, Shuyang Gong, Zhangsong Li, Haodong Zhu
Electronic Communications in Probability, 31:1--12, 2026.
[arXiv] [Journal] [Slides]
- A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials
Zhangsong Li
IEEE Transactions on Information Theory, 72(4):2444--2456, 2026.
[arXiv] [Journal]
- Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter's Threshold Barrier
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
Conference version in Proceedings of 37th SODA, pages 2743--2759, 2026.
[Conference] [Full version]
- Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs
Zhangsong Li
Conference version in Proceedings of 29th APPROX/RANDOM, pages 30:1--30:18, 2025.
[arXiv] [Conference] [Slides]
- Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
Zhangsong Li
IEEE Transactions on Information Theory, to appear.
Conference version in Proceedings of 38th COLT, pages 3580--3581, 2025.
[arXiv] [Conference] [Slides]
- A Computational Transition for Detecting Correlated Stochastic Block Models by Low-Degree Polynomials
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
Annals of Statistics, 54(1):226--251, 2026.
[arXiv] [Journal] [Slides by Jian Ding]
- The Umeyama Algorithm for Matching Correlated Gaussian Geometric Models in the Low-Dimensional Regime
Shuyang Gong, Zhangsong Li
[arXiv] [Slides by Shuyang Gong]
- Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
Jian Ding, Hang Du, Zhangsong Li
Annals of Statistics, 53(5):1833--1856, 2025.
[arXiv] [Journal] [Slides]
- A Polynomial-Time Iterative Algorithm for Random Graph Matching with Non-vanishing Correlation
Jian Ding, Zhangsong Li
Mathematics of Operations Research, online 2025.
[arXiv] [Journal] [Poster]
- A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing Correlation
Jian Ding, Zhangsong Li
Foundations of Computational Mathematics, 25(4):1287--1344, 2025.
[arXiv] [Journal] [Slides]
Talks
- The algorithmic phase transition for correlated spiked models. Peking University Sino-Russian Student Mathematical Seminar, December 2025, Beijing, China.
- Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs (remote talk). The 29th International Conference on Randomization and Computation, August 2025, Berkeley, United States.
- Robust random graph matching in Gaussian models via vector approximate message passing. The 38th Annual Conference on Learning Theory, July 2025, Lyon, France.
- Robust random graph matching in Gaussian models via vector approximate message passing. International Conference on Applied Probability, June 2025, Beijing, China.
- Asymptotic diameter of preferential attachment model (joint with Shuyang Gong). YMSC Probability Seminar, May 2025, Beijing, China.
- Recent progress on random graph matching problems. Tsinghua University, March 2025, Beijing, China.
- Low-degree hardness of detection for correlated Erdős-Rényi graphs. Tsinghua Sanya International Mathematics Forum, January 2024, Sanya, China.
- A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation. Peking University, June 2023, Beijing, China.
Teaching Assistant
Probability Theory, Spring 2025.
Advanced Probability Theory, Fall 2024.
Applied Stochastic Process (Honor), Fall 2023.