Lorenzo Beretta


Lorenzo Beretta

Hi! I am Lorenzo and I am a Goldstine fellow at IBM Cambridge hosted by Kenneth Clarkson. Before joining IBM, I was a postdoc at UCSC hosted by Vaggos Chatziafratis. I did my PhD at BARC, University of Copenhagen, where I was fortunate to be advised by Mikkel Thorup and Mikkel Abrahamsen.

I am a theoretical computer scientist and I study algorithms for massive datasets. My work focuses on sublinear algorithms and high-dimensional geometry.

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

Google Scholar dblp CV

Research

Sublinear Algorithms

Numerous algorithmic innovations in data science stem from the observation that certain tasks 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 a sub-quadratic time approximation scheme for EMD [BR24] [BCJW25].

Selected Publications

More Publications