| Title: | The Complexity of Expansion Problems |
| Advisor: | Dr. Santosh Vempala, School of Computer Science |
| Committee: | Dr. Ton Dieker, School of Industrial and Systems Engineering |
| Dr. Prasad Raghavendra, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley | |
| Dr. Sebastian Pokutta, School of Industrial and Systems Engineering | |
| Dr. Prasad Tetali, School of Mathematics and School of Computer Science | |
| Reader: | Dr. Prasad Raghavendra, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley |
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 spite of over 3 decades of intensive research, the approximability of this parameter remains an open question. The study of this optimization problem has lead to powerful techniques for both upper bounds and lower bounds for various other problems, and interesting conjectures such as the SSE conjecture.
Cheeger's Inequality, a central inequality in Spectral Graph Theory, establishes a bound on expansion via the spectrum of the graph. This inequality and its many (minor) variants have played a major role in the design of algorithms as well as in understanding the limits of computation.
In this thesis we study three notions of expansion, namely edge expansion in graphs, vertex expansion in graphs and hypergraph expansion. We define suitable notions of spectra w.r.t. these notions of expansion. We show how the notion Cheeger's Inequality goes across these three problems. We study 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 relate them to higher eigenvalues of graphs/hypergraphs via 'Higher Order Cheeger's Inequalities'. We also study approximation algorithms for these problems.
Unlike the case of graph eigenvalues, the eigenvalues corresponding to vertex expansion and hypergraph expansion are intractable. We give optimal approximation algorithms and computational lower bounds for computing them.
