Metric Geometry and Computer Science
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.