Matteo Russo
Ph.D. Student in Data Science
Sapienza University of Rome
mrusso(@)diag(.)uniroma1(.)it
About
I am a third year Ph.D. student in Data Science at Sapienza University of Rome, where I am 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.
I am broadly interested in Theoretical Computer Science, with a particular focus in Online Algorithms and Online Learning as well as Algorithmic Game Theory and Clustering.
Publications
Working/Submitted Papers
-
Tight Regret Bounds for Online Learning with Parsimonious Perfect and Imperfect Probes
with Anupam Gupta, Stefano Leonardi
(PDF upon request)
-
Simple and Optimal Sublinear Algorithms for Mean Estimation
with Beatrice Bertolotti, Chris Schwiegelshohn, Sudarshan Shyam
arXiv -
Subspace Preserving Terminal Embeddings with Applications
with Andrew Draganov, Alexander Munteanu, David Saulpic, Chris Schwiegelshohn
(PDF upon request)
-
Anonymous Multi-Agent Contracts
with Johannes Brüstle, Paul Dütting, Stefano Leonardi
(PDF upon request)
-
Contract Design Beyond Hidden Actions
with Tomer Ezra, Stefano Leonardi
arXiv
Published Papers
-
Online Learning in the Random-Order Model
with Andrea Celli, Riccardo Colini Baldeschi, Martino Bernasconi, Federico Fusco, Stefano Leonardi
Conference: ICML 2025
(PDF upon request)
-
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; 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
Teaching
- Tecniche di Programmazione con Laboratorio (Algorithms and Data Structures), Sapienza University of Rome, Spring 2023, 2024, 2025. Teaching Assistant.
Visits and Internships
- Visit to Anupam Gupta at New York University. September 2024-March 2025.
- Visit to Chris Schwiegelshohn at Aarhus University. March 2024.
- Research Intern at Meta UK, hosted by Riccardo Colini Baldeschi. July-November 2023.
- Visit to Chris Schwiegelshohn at Aarhus University. March 2023.
Service
- Program Committee
- EC: 2025
- Reviewer
- EC: 2025
- ESA: 2025
- NeurIPS: 2025
Events
- KmT 2025 - Kolmogorov meets Turing Workshop, LUISS University, Rome, Italy. Invited Speaker.
- WALE 2024 - Workshop on Algorithms for Learning and Economics, Kefalonia, Greece. Invited Speaker.
- HALG 2024 - IGAFIT Highlights of Algorithms Workshop, IDEAS, Warsaw, Poland. Short-Talk and Poster.
- SLMath 2023 - Algorithms, Approximation, and Learning in Market and Mechanism Design, SLMath, Berkeley, USA. Poster.
- ALGA 2023 - Workshop on Algorithms, Learning, and Games, Scicli, Italy. Short-Talk and Poster.
- WALE 2022 - Workshop on Algorithms for Learning and Economics, Naxos, Greece. Poster.