Theory Seminar, Wednesday Nov 5: Nir Petruschka (Weizmann) - The power of recursive embeddings for $\ell_p$ metrics

[Arnold Filtser]

Hi all,

Next week (Wed Nov 5, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker:  Nir Petruschka (Weizmann)
Title: The power of recursive embeddings for $\ell_p$ metrics
Abstract: Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be particularly effective in $\ell_p$ spaces, $p>2$, yielding state-of-the-art results for Lipschitz decomposition, for Nearest Neighbor Search, and for embedding into $\ell_2$. In a nutshell, our method composes metric embeddings by viewing them as reductions between problems, and thereby obtains a new reduction that is substantially more effective than the known reduction that employs a single embedding. We in fact apply this method recursively, oftentimes using double recursion, which further amplifies the gap from a single embedding.

[Arnold Filtser]

The seminar starts in one hour!