Abstract

This talk consists of two different but related results. First, we show how to approximate unique games in minor-closed graph families using linear programming and standard low diameter graph decomposition. We will illustrate the proof through the min-uncut problem. Motivated by this result, we consider graph decompositions using effective resistance as the distance measure, and show that every graph (not just minor-free graphs) has a low effective-resistance diameter graph decomposition.

Video Recording