BARC Talk by Pavel Veselý

Abstract

We consider algorithms for dynamic geometric streams. In this setting, the input is a set of points from the Euclidean space R^d presented as a sequence of insertions and deletions. A streaming algorithm must process this stream of updates in a few passes (ideally just one) using polylogarithmic memory. We focus on the high-dimensional setting, in which the algorithm's space usage must be polynomial (and certainly not exponential) in dimension d.

We present a new algorithmic technique for Uniform Facility Location that breaks the barrier of logarithmic approximation using poly(d) space. Our approach relies on a geometric hashing scheme that maps points in R^d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly(d) distinct buckets.

Joint work with Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Mingwei Yang.