1 of 16

Luca Trevisan�and�Graph Partitioning

​

​

Anupam Gupta �(Courant @NYU)

2 of 16

Luca’s contributions…

graph partitioning for unique games (uses Leighton-Rao/low diameter decomps.)

​

spectral graph partitioning

max-cut

improved Cheeger cuts

k-way cuts

​

fine-grained version for sparsest cut (uses ARV rounding)

​

regularity lemma for low-threshold-rank graphs (extends Frieze-Kannan approach)

​

and his lecture notes making material accessible…

3 of 16

Normalized Laplacians

 

 

 

For simplicity, consider d-regular graphs

 

 

 

 

 

4 of 16

Min-Conductance Cuts

 

 

 

For simplicity, consider d-regular graphs

 

5 of 16

Relaxation?

 

Cheeger’s Inequality [Alon Milman 85]

 

 

 

 

“Easy”

“Hard”

6 of 16

Relaxation?

 

Cheeger’s Inequality [Alon Milman 85]

 

 

 

 

“Easy”

“Hard”

7 of 16

Hard Direction: “if only…”

 

 

 

 

 

 

 

8 of 16

Hard Direction: “if only…”

 

 

 

 

 

 

 

9 of 16

Hard Direction: change of vars

 

 

 

 

 

 

 

10 of 16

Real Proof of Hard Direction

 

 

 

 

 

 

 

same

Let’s not

 

 

 

11 of 16

Real Proof of Hard Direction

 

 

 

 

 

 

 

same

Let’s not

 

 

 

 

 

 

 

 

12 of 16

and that’s the proof…

 

13 of 16

Beyond Cheeger?

 

 

 

[Kwok Lau Lee Oveis Gharan Trevisan STOC 13]

[Lee Oveis Gharan Trevisan STOC 12]

14 of 16

Max-Cut

 

 

For simplicity, consider d-regular graphs

 

 

 

Recurse to get better-than-half without SDPs.

15 of 16

many contributions

graph partitioning for unique games (uses Leighton-Rao/low diameter decomps.)

​

spectral graph partitioning

max-cut

improved Cheeger cuts

k-way cuts

​

fine-grained version for sparsest cut (uses ARV rounding)

​

regularity lemma for low-threshold-rank graphs (extends Frieze-Kannan approach)

​

and his lecture notes making material accessible…

16 of 16

Thanks, Luca!!