Tata Institute of Fundamental Research
The Complexity of Expansion Problems
STCS Seminar
Speaker:
Anand Louis (Princeton University
Department of Computer Science
Princeton, NJ 08544
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 19 Jan 2016, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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.
| Speaker: | Anand Louis (Princeton University Department of Computer Science Princeton, NJ 08544 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 19 Jan 2016, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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.
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.