Lorenzo Beretta

Hi! I am Lorenzo and I am currently a postdoc at University of California, Santa Cruz hosted by Evangelos Chatziafratis. I recently graduated from BARC, University of Copenhagen, where I was fortunate to be advised by Mikkel Thorup and Mikkel Abrahamsen. During my PhD, I visited Aviad Rubinstein at Stanford and I interned at Google Research, where I worked with Vincent Cohen-Addad, Silvio Lattanzi and Nikos Parotsidis.

Research Interests

I am interested in the design and analysis of algorithms for massive datasets, including sublinear algorithms, approximation algorithms and algorithms for geometric problems.

Papers

• Sketched Lanczos uncertainty score: a low-memory summary of the Fisher information
  Marco Miani, Lorenzo Beretta, Søren Hauberg
  NeurIPS 2024 [Code]

• Online sorting and online TSP: randomized, stochastic, and high-dimensional
  Mikkel Abrahamsen, Ioana Bercea, Lorenzo Beretta, Jonas Klausen and László Kozma
  ESA 2024.

• Approximate Earth Mover’s Distance in Truly-Subquadratic Time
  Lorenzo Beretta and Aviad Rubinstein
  STOC 2024

• Multi-Swap k-Means++
  Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi and Nikos Parotsidis
  NeurIPS 2023 [Code]

• Locally Uniform Hashing
  Ioana Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen and Mikkel Thorup
  FOCS 2023

• Online Sorting and Translational Packing of Convex Polygons
  Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta and Linda Kleist
  SODA 2023

• Better Sum Estimation via Weighted Sampling
  Lorenzo Beretta and Jakub Tetek
  SODA 2022, Best Student Paper Award, Invited to HALG 2022 and TALG special issue

• Online Packing to Minimize Area or Perimeter
  Mikkel Abrahamsen and Lorenzo Beretta
  SoCG 2021

• An Optimal Algorithm to Find Champions of Tournament Graphs
  Lorenzo Beretta, Franco Maria Nardini, Roberto Trani and Rossano Venturini
  TKDE (IEEE Transactions on Knowledge and Data Engineering)