BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/649
DTSTAMP:20230914T125933Z
SUMMARY:The Complexity of Expansion Problems
DESCRIPTION:Speaker: Anand Louis (Princeton University\nDepartment of Compu
ter Science\nPrinceton\, NJ 08544\nUnited States of America)\n\nAbstract:
\nAbstract: Graph-partitioning problems are a central topic of research in
the study of algorithms and complexity theory. They are of interest to th
eoreticians with connections to error correcting codes\, sampling algorith
ms\, metric embeddings\, among others\, and to practitioners\, as algorith
ms for graph partitioning can be used as fundamental building blocks in ma
ny 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 leas
t ratio of number of edges cut to size of smaller side of the cut. This ra
tio is known as the expansion of the cut.\n\nIn 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 notion
s of spectra and show how the notion of the celebrated "Cheeger's Inequali
ty" goes across these three problems. I will also talk about higher order
variants of these notions of expansion (i.e. notions of expansion correspo
nding to partitioning the graph/hypergraph into more than two pieces\, etc
.)\, and also about approximation algorithms for these problems.\n
URL:https://www.tcs.tifr.res.in/web/events/649
DTSTART;TZID=Asia/Kolkata:20160119T113000
DTEND;TZID=Asia/Kolkata:20160119T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR