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)

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.