Zhangsong Li
Research
Probability, statistical physics, algorithmic statistics, and theoretical computer science.
Papers
22 papersImproved Rapid Phase Ordering for Ising Dynamics on Random Regular Graphs
Graph Matching in Random Geometric Graphs I: Efficient Algorithms
Efficient Posterior Sampling for Z2 Synchronization
Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
The Conclave Process
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter’s Threshold in the Entire Supercritical Regime
A Smooth Computational Transition in Tensor PCA
Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection
Conference version in Proceedings of 59th ISIT, pages 1--6, 2026.
Asymptotic Diameter of Preferential Attachment Model
Electronic Communications in Probability, 31:1--12, 2026.
A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials
IEEE Transactions on Information Theory, 72(4):2444--2456, 2026.
Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter's Threshold Barrier
Conference version in Proceedings of 37th SODA, pages 2743--2759, 2026.
Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
IEEE Transactions on Information Theory, 72(8):6093--6111, 2026.
Conference version in Proceedings of 38th COLT, pages 3580--3581, 2025.A Polynomial-Time Iterative Algorithm for Random Graph Matching with Non-vanishing Correlation
Mathematics of Operations Research, online 2025.
A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing Correlation
Foundations of Computational Mathematics, 25(4):1287--1344, 2025.
Miscellaneous
PTF Testing Lower Bounds for Planted Subgraphs
Optimal Mixing for the Hardcore Model on Arbitrary Trees at Small Fugacity
Resolution of Vinzant's Conjecture on Phase Retrieval Injectivity
Random 3-Regular Graphs are not Globally Synchronizing
One Standard Deviation Does not Suffice: A Lower Bound for Discrepancy