|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Sketching and embedding are equivalent for norms|
|Date:||Tuesday, January 31|
|Time/Room:||10:30am - 12:30pm/S-101|
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$.