Speaker: |
Rakesh Venkat |

Organiser: |
Rakesh Venkat |

Date: |
Friday, 15 Feb 2013, 14:30 to 16:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

The method is based on the following inequality: $ \lambda_2 \leq \phi(G) \leq O(\sqrt{\lambda_2}) $. Here $lambda_2$ is the second largest eigenvalue of the normalized Laplacian of $G$.

This is a special case of a more general inequality valid on Reimannian manifolds proven by Cheeger, and was adapted to the discrete setting by Alon and Milman.

We shall see a proof of this inequality in the talk, and how it can be used to algorithmically generate a cut with a guarantee on sparsity as above.