Lorenzo Beretta


Lorenzo Beretta

Hi! I am Lorenzo and I am a Herman Goldstine postdoctoral fellow at IBM Cambridge, MA hosted by Kenneth Clarkson. Before joining IBM, I spent a year at UC Santa Cruz hosted by Vaggos Chatziafratis. I completed my PhD at BARC, University of Copenhagen, under the supervision of Mikkel Thorup and Mikkel Abrahamsen. Prior to that, I spent five wonderful years at Scuola Normale Superiore in Pisa.

The goal of my research is to design efficient algorithms for processing large and high-dimensional datasets.

Email: [firstname]2[lastname]@gmail.com

Google Scholar dblp CV

Research

Sublinear Algorithms

Powerful algorithmic innovations originate from the observation that certain problems can be (approximately) solved by algorithms that observe or store only a small fraction of the input, so-called sublinear algorithms. My coauthors and I have developed sublinear algorithms for estimating normalization constants [BT22], counting the number of edges in a graph [BCCS25], and testing whether a function depends only on a few relevant features [BHK25].

High-dimensional Geometry

Several data science tasks involve solving geometric problems over datapoints embedded in high-dimensional spaces. However, the fastest known algorithms for many such problems often run in time exponential in the dimension, reflecting the so-called curse of dimensionality. For instance, computing Optimal Transport or Earth Mover’s Distance (EMD) typically requires time quadratic in the input size or exponential in the dimension. To address this, my coauthors and I developed sub-quadratic time approximation schemes for EMD [BR24] [BCJW25].

Selected Publications

More Publications