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.