Matteo Russo

About

I am a postdoc in the Chair of Discrete Optimization and the Theory Group at EPFL, hosted by Friedrich Eisenbrand.

I completed my PhD in Data Science at Sapienza University of Rome in 2026 where I was fortunate to be advised by Stefano Leonardi.

Before that, I completed my Master's degree in Computer Science at ETH Zurich in 2022, and my Bachelor's degree in Computer Science at Princeton University in 2020.

My research interests are Online Algorithms, Online Learning and Convex Optimization, as well as Algorithmic Game Theory.

Preprints

• Contextual Online Bilateral Trade

  with Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme
  arXiv

• Anonymous Contracts

  with Johannes Brüstle, Paul Dütting, Stefano Leonardi, Tomasz Ponitka
  arXiv

• Multicalibration Yields Better Matchings

  with Riccardo Colini Baldeschi, Simone Di Gregorio, Simone Fioravanti, Federico Fusco, Ido Guy, Daniel Haimovich, Stefano Leonardi, Fridolin Linder, Lorenzo Perini, Niek Tax
  arXiv

• Online Convex Optimization with Sublinear Noisy Probes

  with Simone Di Gregorio, Anupam Gupta, Stefano Leonardi
  (PDF upon request)
  

• Terminal Dimension Reduction for Time Series with Applications

  with Alexander Munteanu, David Saulpic, Chris Schwiegelshohn
  (PDF upon request)
  

Publications

• A Learning Perspective on Random-Order Covering Problems

  with Anupam Gupta, Marco Molinaro
  Conference: SOSA 2026
  arXiv

• Contract Design Beyond Hidden Actions

  with Tomer Ezra, Stefano Leonardi
  Conference: SODA 2026
  arXiv

• Simple and Optimal Sublinear Algorithms for Mean Estimation

  with Beatrice Bertolotti, Chris Schwiegelshohn, Sudarshan Shyam
  Conference: NeurIPS 2025
  arXiv

• Online Learning in the Random Order Model

  with Andrea Celli, Riccardo Colini Baldeschi, Martino Bernasconi, Federico Fusco, Stefano Leonardi
  Conference: ICML 2025
  arXiv

• A Tight VC-Dimension Analysis of Clustering Coresets with Applications

  with Vincent Cohen-Addad, Andrew Draganov, David Saulpic, Chris Schwiegelshohn
  Conference: SODA 2025
  arXiv

• Online Learning with Sublinear Best-Action Queries

  with Andrea Celli, Riccardo Colini Baldeschi, Federico Fusco, Daniel Haimovich, Dima Karamshuk, Stefano Leonardi, Niek Tax
  Conference: NeurIPS 2024
  arXiv

• Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

  with Tomer Ezra, Stefano Leonardi, Michal Pawlowski, William Seeun Umboh
  Conference: APPROX 2024
  arXiv

• Fair Division with Interdependent Values

  with Georgios Birmpas, Tomer Ezra, Stefano Leonardi
  Conference: SAGT 2024
  arXiv

• Low-Distortion Clustering with Ordinal and Limited Cardinal Information

  with Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Chris Schwiegelshohn, Sudarshan Shyam
  Conference: AAAI 2024
  arXiv

• Prophet Inequalities via the Expected Competitive Ratio

  with Tomer Ezra, Stefano Leonardi, Rebecca Reiffenhäuser, Alexandros Tsigonias-Dimitriadis
  Journal: TEAC 2025; Conference: WINE 2024
  arXiv

• Submodular Norms with Applications to Online Facility Location and Stochastic Probing

  with Kalen Patton, Sahil Singla
  Conference: APPROX 2023
  arXiv

• Fully Dynamic Online Selection through Online Contention Resolution Schemes

  with Vashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi, Stefano Leonardi
  Conference: AAAI 2023
  arXiv

Service

Visits and Internships

• Visit to Friedrich Eisenbrand at EPFL. October 2025-January 2026.
• Visit to Anupam Gupta at New York University. September 2024-March 2025.
• Visit to Chris Schwiegelshohn at Aarhus University. March 2023 and March 2024.
• Research Intern at Meta UK, hosted by Riccardo Colini-Baldeschi. July 2023-November 2023.