The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

DAN

Seminar

Expansion of small sets in graphs

Raghavendra, P (Georgia Tech)
Thursday 31 March 2011, 15:30-16:30

Seminar Room 1, Newton Institute

Abstract

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 set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set 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 well-known 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.

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧