Appears in collection : Nexus Trimester - 2016 - Inference Problems Theme

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 from f(x) and f(y) we can estimate the distance between x and y. This problem is a core problem in both the streaming and nearest neighbor search 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 embedding into normed space such as ℓ1.