Student Probability Seminar

---

Approximating the Max Cut Problem

Speaker: Tim Kunisky

Location: Warren Weaver Hall 1314

Date: Wednesday, October 11, 2017, 10 a.m.

Synopsis:

How do you divide the vertices of a graph into two groups with the greatest number of edges going between them? Surprisingly, this simple-sounding problem, called “Max Cut”, can be computationally very difficult. More surprisingly, the state-of-the-art algorithm for approximating the answer (finding a “good” division of vertices) involves “lifting” to a much higher-dimensional problem, and then “projecting” back down to a solution—randomly!

I'll present this classic algorithm, the Goemans-Williamson relax-and-round algorithm, and derive some bounds on its performance. After looking at the algorithm as a geometric relaxation of Max Cut, we’ll discuss how it fits into the algebraic “sum-of-squares hierarchy”, a vast generalization of this technique of algorithm design. Along the way, we’ll have a look at: “semidefinite programming”, a generalization of linear programming that enables such algorithms to be run efficiently; ideas of “pseudo-probability” in the sum of squares hierarchy, probability theory as seen from the point of view of a computationally-bounded agent; and lastly, time permitting, maybe a few formal connections to some models from statistical mechanics.