Speaker: Yi Wu
Title: Hardness of Approximating Satisfiable 3-CSP
Abstract:
A "k-CSP" is a system of constraints over n boolean-valued variables v_i in
which each constraint involves at most k of the variables. Given a k-CSP
instance, Max k-CSP is the algorithmic problem of finding an assignment for
the variables that satisfies the maximum fraction of the constraints. A k-CSP
instance is called "satisfiable" if there is such an assignment that satisfies
all the constraints. For a satisfiable 3-CSP instance, it is NP-hard to find
the optimal assignment; however there is a 5/8-approximation algorithm for the
problem by Zwick [zwi98]. In this talk we will review Zwick's algorithm and
show why it is NP-hard to have a better approximation algorithm assuming
Khot's d-to-1 conjecture.