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