I am an Assistant Professor of Mathematics at UC Davis.
My research is a mix of theoretical computer science, statistics, probability, and data science. More specifically:
CV (updated 1/26/2025)
Family: Melissa (wife), Nicole (sister), Natasha (sister), Maya (sister-in-law)
(10 minutes) A quick intro to the low-degree polynomial framework for detection, recovery, and optimization
Bernoulli-IMS One World Symposium, Aug. 2020
[video] [slides]
(50 minutes) Optimality of AMP Among Low-Degree Polynomials
Banff International Research Station, Aug. 2024
[video] [slides] [paper]
(40 minutes) Fine-Grained Extensions of the Low-Degree Testing Framework
Banff International Research Station, Feb. 2024
[video] [slides] [paper1] [paper2]
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
Alexander S. Wein
[arXiv]
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
ISAAC Congress (International Society for Analysis, its Applications and Computation), 2019
[arXiv]
Notes on Computational-to-Statistical Gaps: Predictions using Statistical Physics
Afonso S. Bandeira, Amelia Perry, Alexander S. Wein
Portugaliae Mathematica, 2018
[arXiv]
Improving the Threshold for Finding Rank-1 Matrices in a Subspace
Jeshu Dastidar, Tait Weicht, Alexander S. Wein
[arXiv]
Stochastic Block Models with Many Communities and the Kesten-Stigum Bound
Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein
COLT 2025
[arXiv]
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
Youngtak Sohn, Alexander S. Wein
STOC 2025
[arXiv]
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
[arXiv]
Statistical Inference of a Ranked Community in a Directed Graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu
STOC 2025
[arXiv]
Tensor Cumulants for Statistical Inference on Invariant Distributions
Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
FOCS 2024
[arXiv]
Low-Degree Phase Transitions for Detecting a Planted Clique in Sublinear Time
Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
COLT 2024
[arXiv] [slides]
Information-Theoretic Thresholds for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
IEEE Transactions on Information Theory, 2025
[arXiv]
Time Lower Bounds for the Metropolis Process and Simulated Annealing
Zongchen Chen, Dan Mikulincer, Daniel Reichman, Alexander S. Wein
[arXiv]
Precise Error Rates for Computationally Efficient Testing
Ankur Moitra, Alexander S. Wein
Annals of Statistics, 2025
[arXiv] [slides]
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Abhishek Dhawan, Cheng Mao, Alexander S. Wein
Random Structures & Algorithms, 2025
[arXiv]
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
COLT 2023
[arXiv] [slides] [video]
Detection-Recovery Gap for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
COLT 2023
[arXiv]
Is it Easier to Count Communities than Find Them?
Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang
ITCS 2023
[arXiv]
Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
Andrea Montanari, Alexander S. Wein
Probability Theory and Related Fields, 2024
[arXiv] [slides]
Near-Optimal Fitting of Ellipsoids to Random Points
Aaron Potechin, Paxton Turner, Prayaag Venkat, Alexander S. Wein
COLT 2023
[arXiv]
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein
STOC 2023
[arXiv] [slides] [video]
Statistical and Computational Phase Transitions in Group Testing
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S. Wein, Ilias Zadik
COLT 2022
[arXiv]
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
NeurIPS 2022 (oral presentation)
[arXiv]
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
David Gamarnik, Aukosh Jagannath, Alexander S. Wein
SICOMP, 2024
[arXiv] [slides] [video]
See also: conference version (FOCS 2020) and related note on circuit lower bounds (Markov Processes And Related Fields, 2024)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna
COLT 2022
[arXiv]
Optimal Spectral Recovery of a Planted Vector in a Subspace
Cheng Mao, Alexander S. Wein
Bernoulli, 2025
[arXiv] [video]
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
MSML 2021
[arXiv]
Optimal Low-Degree Hardness of Maximum Independent Set
Alexander S. Wein
Mathematical Statistics and Learning, 2021
[arXiv] [slides] [video]
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
COLT 2021
[arXiv] [video1] [video2]
Computational Barriers to Estimation from Low-Degree Polynomials
Tselil Schramm, Alexander S. Wein
Annals of Statistics, 2022
[arXiv] [slides] [video]
Free Energy Wells and Overlap Gap Property in Sparse PCA
Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
COLT 2020; Communications on Pure and Applied Mathematics, 2022
[arXiv] [video]
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
IEEE Transactions on Information Theory, 2021
[arXiv]
Computationally Efficient Sparse Clustering
Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
Information and Inference, 2022
[arXiv]
Counterexamples to the Low-Degree Conjecture
Justin Holmgren, Alexander S. Wein
ITCS 2021
[arXiv] [slides] [video]
Subexponential-Time Algorithms for Sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
Foundations of Computational Mathematics, 2023
[arXiv] [slides] [video]
The Kikuchi Hierarchy and Tensor PCA
Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
FOCS 2019; Journal of the ACM (to appear)
[arXiv]
[slides] [video]
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
ITCS 2020
[arXiv]
[slides]
Overcomplete Independent Component Analysis via SDP
Anastasia Podosinnikova, Amelia Perry, Alexander S. Wein, Francis Bach, Alexandre d'Aspremont, David Sontag
AISTATS 2019
[arXiv]
Spectral Methods from Tensor Networks
Ankur Moitra, Alexander S. Wein
STOC 2019, invited to SICOMP special issue (published 2023)
[arXiv]
[slides]
Estimation Under Group Actions: Recovering Orbits from Invariants
Afonso S. Bandeira, Ben Blum-Smith, Joe Kileel, Amelia Perry, Jonathan Weed, Alexander S. Wein
Applied and Computational Harmonic Analysis, 2023
[arXiv]
[slides]
Statistical Limits of Spiked Tensor Models
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira
Annales de l'Institut Henri Poincare (B) Probability and Statistics, 2020
[arXiv]
Message-Passing Algorithms for Synchronization Problems over Compact Groups
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Communications on Pure and Applied Mathematics, 2018
[arXiv]
[slides]
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Annals of Statistics, 2018
[arXiv] [slides]
See also: earlier preprint including "Part II" on synchronization problems
How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, Amelia Perry, Alexander S. Wein
STOC 2016
[arXiv]
[slides]
A Semidefinite Program for Unbalanced Multisection in the Stochastic Block Model
Amelia Perry, Alexander S. Wein
SampTA 2017
[arXiv]
Statistical Estimation in the Presence of Group Actions
Ph.D thesis, Massachusetts Institute of Technology, 2018
[PDF]
[slides]