University of California, Davis

Office: Mathematical Sciences Building 2138

My last name is pronounced "wine"

Pronouns: he/him/his

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:

- Math of data science: what are the optimal algorithms for finding a hidden structure buried in random noise, and under what conditions is this even possible?
- Computational complexity of statistical inference, particularly in the low-degree polynomial model of computation
- Tensors (multi-dimensional arrays) and associated computational challenges
- Connections between Bayesian inference and statistical physics
- Problems involving group actions (e.g. determining 3-dimensional molecular structure via cryo-electron microscopy), including connections to representation theory and invariant theory

CV (updated 1/20/2024)

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]

(40 minutes) Fine-Grained Extensions of the Low-Degree Testing Framework

*Banff International Research Station, Feb. 2024*

[video] [slides]

(50 minutes) Is Planted Coloring Easier than Planted Clique?

*GRAMSIA Workshop, Harvard, May 2023*

[video] [slides] [paper]

(1 hour) Average-Case Computational Complexity of Tensor Decomposition

*Institute for Advanced Study, Oct. 2022*

[video] [slides] [paper]

**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]

**Tensor Cumulants for Statistical Inference on Invariant Distributions**

Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein

[arXiv]

**Low-Degree Phase Transitions for Detecting a Planted Clique in Sublinear Time**

Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein

[arXiv] [slides]

**Information-Theoretic Thresholds for Planted Dense Cycles**

Cheng Mao, Alexander S. Wein, Shenduo Zhang

[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

[arXiv] [slides]

**Detection of Dense Subhypergraphs by Low-Degree Polynomials**

Abhishek Dhawan, Cheng Mao, Alexander S. Wein

[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

[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 (to appear)*

[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*

[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]