5 citations · 19 across the 24 of their papers we have counts for
6 papers · 1 filter
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Ofer Grossman, Meghal Gupta, Mark Sellke
We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. In 1978, Morris famously gave a randomized algorithm achi…
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Online Multiserver Convex Chasing and Optimization
Sébastien Bubeck, Yuval Rabani, Mark Sellke
We introduce the problem of -chasing of convex functions, a simultaneous generalization of both the famous k-server problem in , and of the problem of chasing convex bodies…
Vertex Sparsifiers for c-Edge Connectivity
Yang P. Liu, Richard Peng, Mark Sellke
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve all edge-connectivity values up to c between a set of k terminal vertices, where f(c) is a function that on…
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li +1
Let be a family of sets in some metric space. In the -chasing problem, an online algorithm observes a request sequence of sets in and respo…