Computer Science/Discrete Mathematics Seminar I

Earthmover metrics are popular similarity measures in computer vision, and they are also used in the design of approximation algorithms for classification problems. Motivated by the existing nearest neighbor search databases for L_1 metrics, it was asked whether Earthmover metrics embed into L_1 with bounded distortion. In this talk we will discuss two analytic methods showing that such metrics do not embed into L_1 in the case when the underlying metric space is a large dimensional hypercube or a fine mesh in the plane. Based on joint works with Subhash Khot and Gideon Schechtman.