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