Random space partitions and optimal transport: beyond metric embeddings
October 16, 2019 (GHC 6115)

I will talk about two new results (both joint with Yihe Dong, Piotr Indyk and

Tal Wagner):

* A new algorithm that finds nearest-neighbor-friendly partitions of a

high-dimensional space using graph partitioning coupled with supervised learning

(e.g., neural networks) https://arxiv.org/abs/1901.08544

* A new algorithm for optimal transport based on tree approximations

https://arxiv.org/abs/1910.04126

The unifying theme is going beyond low-distortion embeddings into simple metric

spaces.