Lucas Pesenti

I am a fourth-year Ph.D. student in Statistics and Computer Science at Bocconi University. I was advised by Luca Trevisan, and I am now advised by Laura Sanità and co-advised by Pravesh Kothari. Before that, I studied at École Normale Supérieure de Paris and got my M.Sc. in Computer Science from the Parisian Master of Research in Computer Science.

I am broadly interested in theoretical computer science, with a preference for approximation algorithms and applications of continuous methods to discrete mathematics.

Email: lucas dot pesenti at phd dot unibocconi dot it

1. Fourier Analysis of Iterative Algorithms
with Chris Jones
in submission [arXiv]

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, enabling us to implement heuristic cavity-based reasoning into rigorous arguments.

2. New SDP roundings and certifiable approximation for cubic optimization
with Tim Hsieh, Pravesh Kothari, and Luca Trevisan
in SODA 2024 [Slides] [arXiv]

We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the hypercube or the sphere, complementing the rich theory of SDP roundings for the quadratic case. This answers a question of Trevisan regarding the existence of certificates on the optimum value of cubic polynomials matching the guarantees of a search algorithm of Khot and Naor.

3. Discrepancy minimization via regularization
with Adrian Vladu
in SODA 2023 [Slides] [arXiv]

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