The Complexity of Expansion Problems

Graph-partitioning problems are a central topic of research in the study of algorithms and complexity theory. They are of interest to theoreticians with connections to error correcting codes, sampling algorithms, metric embeddings, among others, and to practitioners, as algorithms for graph partitioning can be used as fundamental building blocks in many applications. One of the central problems studied in this field is the sparsest cut problem, where we want to compute the cut which has the least ratio of number of edges cut to size of smaller side of the cut. This ratio is known as the expansion of the cut. 

In this talk, I will discuss three notions of expansion - edge expansion in graphs, vertex expansion in graphs and edge expansion in hypergraphs. I will define suitable notions of spectra and show how the notion of the celebrated "Cheeger's Inequality" goes across these three problems. I will also talk about higher order variants of these notions of expansion (i.e. notions of expansion corresponding to partitioning the graph/hypergraph into more than two pieces, etc.), and also about approximation algorithms for these problems.