Computer Science/Discrete Mathematics Seminar II

Sketching for distance estimation is the problem where we need to design a possibly randomized function $F$ from a metric space to short strings, such that for any points $x,y$ from the metric space, the "sketches" $F(x)$ and $F(y)$ are sufficient to estimate the distance between $x$ and $y$. This problem is a core problem in modern algorithmic design toolbox, for example for problems both the streaming and high-dimensional geometry areas. We will discuss this problem and its connections to the theory of metric embeddings. In particular, we will discuss when and why sketching is equivalent to bi-Lipschitz embedding into normed space such as $\ell_1$.