Fall 2017

Low Diameter Graph Decompositions and Approximating Unique Games

Thursday, Sep. 14, 2017 11:30 am12:00 pm

Add to Calendar

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.