Metric Geometry and Computer Science

The combinatorial landscape is fraught with complexity. Computing optimal solutions to natural problems is often intractable, and understanding discrete systems can be difficult without the presence of richer structures to guide our intuition. When we are able to geometrize a system or to realize our combinatorial structures as part of a larger geometry, there is the potential to greatly increase our depth of understanding. This allows us to employ powerful tools and intuitions developed in fields like non-linear functional analysis, Riemannian geometry, and geometric group theory.

This talk focuses on two examples. The first involves low-distortion embeddings of finite metric spaces, and its application to algorithms and structural theorems for cuts, flows, and balanced separators in graphs. The second revolves around abstract notions of dimension and how they can be used to characterize the complexity of certain problems on metric spaces and networks. In each case, I will discuss how the techniques developed in solving computational problems have not only borrowed from known geometric tools, but have contributed back to those communities as well.

The talk is intended for a general CS audience.