AI Center Seminar - AI Fundamentals series - Prof. Alex Wein

The talk is jointly organized by the EPFL Foundations of Learning and AI Research (FLAIR) group and the EPFL AI Center.

Hosting professor: Prof. Florent Krzakala

Title
Connecting Statistical Physics and Low-Degree Polynomials

Abstract
I will discuss some progress on rigorously connecting different forms of average-case computational hardness: "geometric" methods rooted in statistical physics, and "algebraic" methods based on low-degree polynomials. I will mention the following results:
(1) the "Franz-Parisi criterion" (arXiv:2205.09727) joint with Bandeira, Alaoui, Hopkins, Schramm, Zadik
(2) equivalence of approximate message passing and low-degree polynomials (arXiv:2212.06996) joint with Montanari
(3) recovering the Kesten-Stigum threshold in community detection with low-degree polynomials (arXiv:2503.03047) joint with Chin, Mossel, Sohn

Bio
Alex Wein, is Assistant Professor of Mathematics at UC Davis. His 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