Theory Seminar

Separating MAX 2-AND, MAX DI-CUT and MAX CUT

Aaron PotechinUniversity of Chicago
3725 Beyster BuildingMap
In 2008, Raghavendra’s paper “Optimal algorithms and inapproximability results for every CSP?” showed that assuming the Unique Games Conjecture (or at least that unique games is hard), for any CSP on a finite set of predicates, the optimal worst-case polynomial time approximation algorithm is to use a standard semidefinite program and then apply a rounding algorithm. However, since the set of potential rounding functions is extremely large, Raghavendra’s result does not tell us what the approximation ratio is for a given CSP. In fact, there are still several basic questions which are still open. For example, the question of whether there is a 7/8 approximation ratio for MAX SAT (where the clauses can have any length) is still open.

In this talk, I will review Raghavendra’s result and why additional work is needed to analyze particular CSPs. I will then describe why MAX 2-AND, MAX DI-CUT and MAX CUT all have different approximation ratios and how we can prove this.

This is joint work with Joshua Brakensiek, Neng Huang, and Uri Zwick


Greg Bodwin


Euiwoong Lee