Aleksandar Nikolov, University of Toronto

Abstract

I will introduce the theory of average distortion embeddings, which has recently seen rapid development. Average distortion embeddings relax bi-Lipschitz embeddings, and in some cases they allow for much lower distortion. A striking example is Naor’s average John theorem, showing that *any* d-dimensional normed space embeds into Euclidean space with average distortion O(sqrt(log d)), in contrast to the sqrt(d) distortion necessary for a bi-Lipschitz embedding. Additionally, the ell_p and Schatten-p spaces embed into ell_1 with dimension-independent average distortion. At the same time, average distortion embeddings retain some of the algorithmic applications of bi-Lipschitz embeddings. In particular, an average distortion embedding of a metric space M into Euclidean space or into ell_1 implies a data-dependent LSH scheme for M, and, therefore, an efficient near neighbor search data structure. In addition to describing these results, I will also give some open problems about making average distortion embeddings computationally efficient.

Video: [Part one]  [Part two]