Talks & Seminars
Title: The complexity of expansion problems
Dr. Anand Louis, Princeton University
Date & Time: January 21, 2016 14:00
Venue: Conference Room, C Block, 01st Floor, Dept. of CSE, Kanwal Rekhi (KReSIT) Bldg.
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 Profile:
Dr. Anand Louis is postdoctoral researcher in the Department of Computer Science at Princeton University. More details about him are available at http://www.cs.princeton.edu/~alouis/#me.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback