COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Expansion of small sets in graphs

## Expansion of small sets in graphsAdd to your list(s) Download to your calendar using vCal - Raghavendra, P (Georgia Tech)
- Thursday 31 March 2011, 15:30-16:30
- Seminar Room 1, Newton Institute.
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 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. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsLondon Office of Tibet Cambridge Volcanology Social Enterprise and International Development## Other talksA continuum theory for the fractures in brittle and ductile solids Communicating Your Research to the Wider World Prof Kate Jones (UCL): Biodiversity & Conservation Investigation into appropriate statistical models for the analysis and visualisation of data captured in clinical trials using wearable sensors Mechanical performance of wall structures in 3D printing processes: theory, design tools and experiments Joinings of higher rank diagonalizable actions |