research
∙
05/15/2023
Sparsifying Sums of Norms
For any norms N_1,…,N_m on ℝ^n and N(x) := N_1(x)+⋯+N_m(x), we show ther...
share
research
∙
09/09/2022
Spectral hypergraph sparsification via chaining
In a hypergraph on n vertices where D is the maximum size of a hyperedge...
research
∙
11/21/2021
Multiscale entropic regularization for MTS on general metric spaces
We present an O((log n)^2)-competitive algorithm for metrical task syste...
research
∙
07/20/2021
Non-existence of annular separators in geometric graphs
Benjamini and Papasoglou (2011) showed that planar graphs with uniform p...
research
∙
06/10/2019
Pure entropic regularization for metrical task systems
We show that on every n-point HST metric, there is a randomized online a...
research
∙
11/06/2018
Flow-Cut Gaps and Face Covers in Planar Graphs
The relationship between the sparsest cut and the maximum concurrent mul...
research
∙
07/12/2018
Metrical task systems on trees via mirror descent and unfair gluing
We consider metrical task systems on tree metrics, and present an O(dept...
research
∙
11/06/2017
Fusible HSTs and the randomized k-server conjecture
We show that a potential-based algorithm for the fractional k-server pro...
research
∙
11/03/2017