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.