Sketching and embedding are equivalent for norms

Computer Science/Discrete Mathematics Seminar II
Topic:Sketching and embedding are equivalent for norms
Speaker:Alex Andoni
Affiliation:Columbia University
Date:Tuesday, January 31
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2017/0131-AlexAndoni

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$.