Department of Mathematics

Office: Warren Weaver Hall 827

My last name is pronounced "wine" (like the drink)

Pronouns: he/him/his

I am a Courant Instructor (postdoc) at NYU's Courant Institute. I am partially funded by the Simons Collaboration on Algorithms and Geometry. During Fall 2021, I will be a Simons-Berkeley Research Fellow in this program at the Simons Institute. I will also be on the job market at that time.

My research interests include:

- statistical and computational limits of problems arising in machine learning and high-dimensional statistics,
- low-degree polynomials as a restricted model of computation,
- connections between Bayesian inference and statistical physics,
- problems involving group actions (e.g. cryo-EM image processing), including connections to representation theory and invariant theory.

CV (updated 12/16/2020)

(10 minutes) A quick intro to the low-degree polynomial method for detection, recovery, and optimization

*Bernoulli-IMS One World Symposium, Aug. 2020*

[video] [slides]

(50 minutes) The low-degree method for (detection and) recovery

*Stanford ISL Colloquium, Oct. 2020*

[video] [slides] [paper]

(45 minutes) The low-degree method for random optimization problems

*Simons Institute Workshop on Learning and Testing in High Dimensions, Dec. 2020*

[video] [slides] [paper1] [paper2]

**Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio**

Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira

[arXiv]

**Notes on Computational-to-Statistical Gaps: Predictions using Statistical Physics**

Afonso S. Bandeira, Amelia Perry, Alexander S. Wein

*Portugaliae Mathematica, 2018*

[arXiv]

**Optimal Spectral Recovery of a Planted Vector in a Subspace**

Cheng Mao, Alexander S. Wein

[arXiv]

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

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

**Computational Barriers to Estimation from Low-Degree Polynomials**

Tselil Schramm, Alexander S. Wein

[arXiv] [slides] [video]

**Free Energy Wells and Overlap Gap Property in Sparse PCA**

Gérard Ben Arous, Alexander S. Wein, Ilias Zadik

*COLT 2020*

[arXiv] [video]

**The Average-Case Time Complexity of Certifying the Restricted Isometry Property**

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira

[arXiv]

**Computationally Efficient Sparse Clustering**

Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira

[arXiv]

**Low-Degree Hardness of Random Optimization Problems**

David Gamarnik, Aukosh Jagannath, Alexander S. Wein

*FOCS 2020*

[arXiv] [slides] [video]

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

[arXiv] [slides] [video]

**The Kikuchi Hierarchy and Tensor PCA**

Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore

*FOCS 2019*

[arXiv]
[slides]

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

[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

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

**Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization**

Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra

[arXiv]

(Partially subsumed by journal version above)

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