Expansion of small sets in graphs
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Mustapha Amrani.
Discrete Analysis
A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small setexpander, from a graph containing a small nonexpanding set of vertices. This problem henceforth referred to as the SmallSet Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the wellknown Unique Games Conjecture—a conjecture that has numerous implications in approximation algorithms.
In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
