Computer Science/Discrete Mathematics Seminar II

Algorithmic graph partitioning tasks are naturally related to geometric issues. Over the past decades, several deeper connections of this type have emerged. In this talk, we will describe one example by showing that, up to lower order factors, the integrality gap of the Goemans—Linial semidefinite programming relaxation for the Sparsest Cut problem with general capacities and demands is of order $\sqrt{\log n}$. The final step here was obtained recently in joint work with Robert Young (NYU), which is a culmination of more than two decades of work on this question. It relies on intricate geometric properties of the Heisenberg group. The purpose of this presentation, which does not assume prior familiarity with the relevant concepts and objects, is to provide a gentle introduction to the cast of characters that appear here, give detailed examples of how one could reason about them, and explain how it all comes together to obtain the aforementioned algorithmic statement.