Lucas Pesenti

I am a postdoctoral researcher at ETH Zurich, hosted by David Steurer.
I graduated from the Ph.D. program in Statistics and Computer Science of Bocconi University. I was advised by Luca Trevisan, and then by Laura Sanità and Pravesh Kothari. Before that, I studied at École Normale Supérieure de Paris and got my M.Sc. from the Parisian Master of Research in Computer Science.

My research interests lie in theoretical computer science, with a focus on approximation algorithms, their connections with statistical physics and random matrix theory, and applications of continuous methods to discrete mathematics.

Email: lpesenti at ethz dot ch
Office: Z24 (OAT building, 21st floor)

We study the dynamics of first-order methods through the limiting traffic distribution of the input matrix. This yields the first analysis of Approximate Message Passing (AMP) on nontrivial deterministic matrices, resolving parts of conjectures of Marinari, Parisi, and Ritort (1990), and leads to a new general AMP iteration whose limiting dynamics are conditionally Gaussian, answering questions of Wang, Zhong, and Fan (2022).

We establish a tighter connection between (1) how well the indicator function of a set can be approximated by low-degree polynomials in Gaussian space, and (2) the Gaussian surface area of that set. As a consequence, we obtain improved agnostic learning algorithms for several concept classes.

We introduce a new approach for analyzing a broad class of nonlinear iterative algorithms on random matrices using Fourier analysis. As the dimension of the input matrix goes to infinity, the Fourier basis simplifies, allowing us to implement heuristic cavity-based reasoning into rigorous arguments.

We present rounding schemes for semidefinite programming relaxations of the problem of maximizing cubic polynomials over the hypercube or the sphere, complementing the well-developed theory for quadratic polynomials. This answers a question posed by Trevisan on the existence of certificates for the optimum value of cubic polynomials matching the guarantees of a search algorithm of Khot and Naor.

We analyze a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to reinterpret several breakthrough results in algorithmic discrepancy theory, ranging from Spencer's theorem to Banaszczyk's bounds.

The union bound is a classical tool in the probabilistic method for proving the existence of objects with extremal features. In my Ph.D. thesis, I present an alternative approach: proving existence through the design and analysis of algorithms from continuous optimization that explicitly construct the desired objects.