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 talk about higher order variants of expansion (i.e. notions of expansion corresponding to partitioning the graph into more than two pieces, etc.), and how they relate to the graph’s eigenvalues. The proofs will also show how to use the graph’s eigenvectors to compute partitions satisfying these bounds. Based on joint works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.

- All seminars.
- Seminars for 2017

Last updated: 06 Jun 2023