ARC Colloquium - Neng Huang

Talk title: New Worst-Case Approximability Results for MAX CSPs

Abstract:  In his breakthrough result, Raghavendra showed that the worst-case approximation ratios of all MAX CSPs are given by a canonical semidefinite programming (SDP) relaxation called the Basic SDP, assuming the Unique Games Conjecture. Furthermore, there exists a polynomial-time rounding algorithm for the Basic SDP that achieves these approximation ratios up to any additive error. It would seem that these results have completely settled the issue of worst-case approximation for MAX CSPs. In this talk, we will explain why this isn't the case, and present some recent results in this direction, including: (1) MAX NAE-SAT does not have a 7/8-approximation algorithm, and (2) the approximation ratio of MAX DI-CUT is strictly between those of MAX CUT and MAX 2-AND. Both results assume UGC. Based on joint work with Joshua Brakensiek, Aaron Potechin and Uri Zwick.