Metric embeddings

Objectives and Course Description

Given an n point metric space X, how close it is to being a subset of some Euclidean space/specific normed space? This problem has spurred a lot of activity in the last 50 or so years in theoretical computer science, data science and pure mathematics.

On the practical side, such representations arise when we wish to approximately solve combinatorial optimisation problems in graphs, or in general when we wish to use linear methods to solve non-linear problems. Specific applications range from the sparcest cut problem, multicommodity flow to clustering algorithms. An important application is also the dimension reduction method of Johnson and Lindenstrauss, which is widely used in randomised algorithms.

In theory, studying these embedding problems tells us deep properties about the geometry of X, and of the normed spaces where X embeds. The tools for constructing embedding are elaborate and often involving probability, and the proofs that no embedding exists are quite profound. Indeed, the tools involve differentiability, Poincare inequalities, and the structure of finite perimeter sets – a lot of hard core GMT! On the other side of the coin, the questions in Banach spaces lead to the rich Ribe-program, and some very delicate strengthening of the triangle inequality.

In this course, the goal is to get a taste of all three: the applications to computer science and data analysis, the tools from geometry of metric spaces, and the deep questions on Banach space geometry. This will be a mathematical and proof based course – we define everything and prove most things we say. We also aim to bring this close to contemporary research and mention open problems. In the interactive HW, we look at important research papers and learn skills to read them.

Prerequisites: A solid mathematical maturity (=not afraid of proofs), and a bit of metric spaces and probability will be helpful. Functional analysis/Hilbert spaces is also used quite a bit. But, most of the facts we use are presented at least a little, and feel free to ask about giving more background!

HWs:

We will have interactive HW assignments, where each week we go over (parts) of an important paper. The paper is referenced in the lecture notes, and shared a week before the assignemnt. You should read a little of the paper before the HW and think of the problems.

We will discuss the problems in the session. These problems will ask about the paper, its main results, applications thereof and the main tools. We will try to break up the paper and understand at least some part of it.

If you can not attend, you can send me via email your written answers to the problems.

LEcture times

Lectures: Sylvester Eriksson-Bique

Tuesday + Wednesday 18.10-10.12.2025

08:30-10:00 MaD 355

HW sessions:

Wed 5.11- 10.12.2025
10:15-12:00 MaD 355