Matteo Russo (original) (raw)
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.