This post continues describing our series of online seminars devoted to accessible presentations of some of the most significant mathematical theorems of the 21st century. I am delighted to report that on February 11 Prof. Avi Wigderson delivered a beautiful and highly accessible lecture on expander graphs. If you missed the talk, the recording is now available on YouTube.
The next lecture in the series will take place on Prof. Assaf Naor (Princeton University, USA) will speak on the topic of The Sparsest Cut Problem.
To join the talk, simply click here at the scheduled time. No registration is required. For a full list of upcoming seminars, please visit the seminar webpage: https://th21.le.ac.uk/next-talks/.
For announcements of other talks, as well as descriptions of recent major mathematical breakthroughs, see the full list of posts on this blog.
The sparsest cut problem. The sparsest cut problem is a central combinatorial optimization problem with deep connections to geometry, analysis, and theoretical computer science. Given a finite graph , the goal is to partition the vertex set into two nonempty parts so as to minimize the ratio The minimum possible value, is known as the edge expansion (or Cheeger constant) of .
Computing exactly is NP-hard. Nevertheless, efficient approximation algorithms have been developed. In 1999, Leighton and Rao (Leighton and Rao 1999) obtained a polynomial-time -approximation algorithm: for every -vertex graph , one can find a cut with ratio at most .
A major breakthrough came in 2009, when Arora, Rao and Vazirani (Arora, Rao, and Vazirani 2009) improved the approximation ratio to . Thus there exists a polynomial-time algorithm producing a cut satisfying
The weighted problem and the recent breakthrough.
A more general and substantially more delicate version is the sparsest cut problem with general capacities and demands. Here we are given two symmetric matrices and with nonnegative entries. The matrix encodes edge capacities, while encodes demands between pairs of vertices.
For any nonempty proper subset , define The objective is to minimize .
In a recent paper (Chang, Naor, and Ren 2024), accepted for publication in Acta Mathematica, Chang, Naor and Ren proved a polynomial-time approximation algorithm when the number of nonzero entries of is at most . More precisely, the algorithm outputs a subset satisfying This matches the best possible asymptotic bound and settles a long-standing open problem.
Geometry behind the algorithms.
The proof draws on deep ideas from the geometry of metric spaces and the phenomenon of measure concentration. The guiding principle is to represent the vertices of a graph as points in a suitable metric space so that distances reflect combinatorial structure. Once such an embedding is constructed, one can partition the graph according to geometric clusters in the target space.
Semidefinite programming provides an efficient way to construct these embeddings. The quality of the resulting cut depends on the distortion of the embedding: better distortion yields better approximation ratios.
A metric space admits a bi-Lipschitz embedding into a metric space if there exist constants and a mapping such that The ratio is called the distortion of the embedding. Minimizing distortion is a classical theme in geometric functional analysis, with powerful algorithmic consequences.
In 1985, Bourgain proved that every -point metric space embeds into a Euclidean space with distortion . For general metrics this bound is essentially optimal. However, improved bounds are possible for special classes.
One such class is that of metrics of negative type. A finite metric space with points is of negative type if for all real numbers satisfying ,
In 2008, Chawla, Gupta and Räcke (Chawla, Gupta, and Räcke 2008) proved that every -point metric space of negative type embeds into Euclidean space with distortion . Shortly thereafter, Arora, Lee and Naor (Arora, Lee, and Naor 2008) improved this to .
The recent breakthrough of Chang, Naor and Ren (Chang, Naor, and Ren 2024) sharpens this to the optimal bound matching a lower bound of Enflo (1969). This optimal embedding theorem directly yields the optimal approximation algorithm for the sparsest cut problem with general capacities and demands.
Prof. Naor’s lecture will present these ideas in an accessible way, explaining how geometric insights about metric embeddings ultimately lead to optimal algorithms for fundamental combinatorial optimization problems.