5 citations · 5 across the 7 of their papers we have counts for
10 papers
The Online Steinitz Problem
Matteo Russo, Jiaye Wei
Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem:…
Dimension-Free Rank Lifting from Random Hyperplane Arrangements
Luca Becchetti, Matteo Russo, Ruben Skorupinski
We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset of , …
Moment Ambiguity and the Limits of Robust Stochastic Optimization
Andrés Cristi, Matteo Russo, Jiechen Zhang
We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified fram…
Terminal Dimension Reduction for Time Series with Applications
Alexander Munteanu, Matteo Russo, David Saulpic +1
Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points , a terminal embedding is a mapping $f:\mathbb{R}^d\righta…
Online Convex Optimization with Sublinear Noisy Probes
Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1
We study Online Convex Optimization (OCO) over a convex set , where in each round the learner selects and then observes a convex loss $f_t:K\…
Nearly-Tight Bounds for Zonotope Containment and Beyond
Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo +1
We investigate the convex-body containment problem , where the outer body is described by a membership oracle and the inne…
A Tight VC-Dimension Analysis of Clustering Coresets with Applications
Vincent Cohen-Addad, Andrew Draganov, Matteo Russo +2
We consider coresets for -clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the -median objective $\sum_…
Simple and Optimal Sublinear Algorithms for Mean Estimation
Beatrice Bertolotti, Matteo Russo, Chris Schwiegelshohn +1
We study the sublinear multivariate mean estimation problem in -dimensional Euclidean space. Specifically, we aim to find the mean of a ground point set , which minimizes…
Low-Distortion Clustering with Ordinal and Limited Cardinal Information
Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs +3
Motivated by recent work in computational social choice, we extend the metric distortion framework to clustering problems. Given a set of agents located in an underlying metric…
Submodular Norms with Applications To Online Facility Location and Stochastic Probing
Kalen Patton, Matteo Russo, Sahil Singla
Optimization problems often involve vector norms, which has led to extensive research on developing algorithms that can handle objectives beyond the norms. Our work introd…