Manhattan distances, Metric Transforms, and Kernels

Speaker: Timothy Chu , Carnegie Mellon University (CMU)

Date: Wednesday, March 10, 2021

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes


Event Type: Seminar

Room Description:

Host: Quanquan Liu, MIT

Contact: Quanquan Liu,

Relevant URL:

Speaker URL:

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Manhattan distances, Metric Transforms, and Kernels

Take n points in any dimension, compute the Manhattan distance between each pair of points, and take the π/4 power of each distance. The resulting distances will always be a Manhattan distance. Can you prove why?

In our work, we classify all functions f that send Manhattan distances to Manhattan distances. We also classify all functions f that send Manhattan distances to inner products, a fundamental question related to kernels in machine learning. The tools we use include the Hadamard transform, Abelian group representation theory, probability theory, and linear algebra.

The Euclidean analog of our work was established by Von Neumann and Schoenberg from 1937-1942 (Annals of Math ‘37, ‘38, ....). The Euclidean analog is the foundation of kernel methods, harmonic analysis of semi groups, and was recently used to show that sketching and embedding of norms were equal(AKR, STOC ‘15).

We will provide a number of open problems related to this topic. No special background will be needed to enjoy this talk!

Joint work with Gary Miller, Shyam Narayanan, and Mark Sellke. Link to paper:

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2021.

Created by Quanquan Liu Email at Tuesday, March 02, 2021 at 1:17 AM.