Functions that Preserve Manhattan Distances
February 3, 2021 (Zoom - See email or contact organizers for link)

Abstract: Let's say you take n points, compute the Manhattan distance between each pair of points, and take the 2/3 power of each distance. The resulting distances will always be a Manhattan distance!

Can you prove why? This is an extension of classical work by Issai Schoenberg in the 1930s who addressed the same problem for Euclidean distances. Schoenberg's work is the cornerstone of all kernel methods in machine learning.

In our talk, we provide a full classification of functions that send Manhattan distances to Manhattan distances. We use ideas from group representation theory, calculus, and more. One consequence of our work is that we provide a full classification of positive definite kernels in the Manhattan distance setting.

Joint work with Gary Miller, Mark Sellke, and Shyam Narayanan.