#### Theory Seminar

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

Aaron PotechinUniversity of Chicago

WHERE:

3725 Beyster BuildingMap

WHEN:

Friday, December 1, 2023 @ 2:00 pm - 3:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

SHARE:

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