L1 embeddings and flow-cut gaps

This mini-workshop will be an introduction to the field of multi-commodity flow/cut gaps in graphs and their intimate relationship with embeddings of finite metric spaces. A primary goal is to cover two of the most useful techniques for upper and lower bounds: Random embeddings and coarse differentiation, respectively. Our other goal is to highlight the many beautiful and fundamental problems that are still left open. The final talk will discuss some generalizations of the classical model that arise from considerations in wireless networks.

Organized by James R. Lee



Tuesday, June 19
3:20-4:05 James R. Lee Embeddings, flows, and cuts: An Introduction
Since the works of Linial-London-Rabinovich and Aumann-Rabani, L1 embeddings of graph metrics have been used to study multi-commodity flow/cut gaps in various families of graphs. I will survey this connection, the known results on flow/cut gaps, as well as the major open problems and the most prominent embedding techniques.
4:05-4:50 Tasos Sidiropoulos Random embeddings
Random embeddings are a powerful tool in reducing the topological complexity of a graph while approximately preserving its metric structure. We will discuss the power and limitations of such methods and how they can be used to reduce the GNRS conjecture to a pair of manifestly simpler ones. We will end by exhibiting an optimal way of random planarizing a bounded-genus surface.
4:50-5:20 (coffee break)
5:20-6:05 Mohammad Moharrami Lower bounds from coarse differentiation
A fundamental result from Rademacher states that any Lipschitz map from $\mathbb{R}^n$ to $\mathbb{R}^m$ is differentiable almost everywhere. This in effect implies that Lipschitz maps from $\mathbb{R}^n$ to $\mathbb{R}^m$ are locally (at the limit) linear almost everywhere. A notion of coarse differentiation was then introduced by Eskin, Fisher and Whyte as a generalization of Rademacher's theorem to find local rigid structures for maps between arbitrary metric spaces. This talk will include a brief introduction to metric embeddings and coarse differentiation. Then, it will focus on applications of coarse differentiation in proving lower bounds for embeddings, and analyzing the SDP relaxation of the sparsest cut problem.
6:05-6:50 Sreeram Kannan Cuts and flows in polymatroidal networks

The well-known maxflow-mincut theorem for single-commodity flows in directed networks is of fundamental importance in combinatorial optimization. Flow-cut equivalence does not hold in the multicommodity case. A substantial amount of research in the algorithms community has focused on understanding the gap between multicommodity flows and associated cuts. Poly-logarithmic gap results have been established in various settings via tools from network decomposition and metric embeddings.

In this talk we describe work that obtains flow-cut gap results in *polymatroidal* networks. In these networks there are submodular capacity constraints on the edges incident to a node. Such networks were introduced by Lawler & Martel and Hassin in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles. The well-known maxflow-mincut theorem for a single- commodity holds in polymatroidal networks, however, the multicommodity case has not been previously explored. Our work is primarily motivated by applications to information flow in wireless networks although the technical results we obtain are of independent interest as they generalize known results in standard networks including node-capacitated undirected networks. The results highlight the utility of line embeddings suggested by Matousek and Rabinovich. We use them to round the dual of the flow-relaxation rewritten with a convex objective function obtained from the Lovasz-extension of a submodular function.