Alex Wein

Contact Information

Courant Institute of Mathematical Sciences, New York University
Department of Mathematics
Office: Warren Weaver Hall 827


My last name is pronounced "wine" (like the drink)
Pronouns: he/him/his

About Me

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:

CV (updated 12/16/2020)


Some Recorded Talks [see more]

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


Surveys

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]


Publications/Preprints

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]


Thesis

Statistical Estimation in the Presence of Group Actions
Ph.D thesis, Massachusetts Institute of Technology, 2018
[PDF] [slides]