We study the approximability a natural Boolean constraint satisfaction problem: Horn satisfiability. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a near-satisfiable instance.

Given an instance of Max Horn-3SAT that admits an assignment satisfying $(1-\eps)$ of its constraints for some small constant $\eps > 0$, it is hard to find an assignment satisfying more than $(1-1/O(\log (1/\eps)))$ of the constraints. This matches a linear programming based algorithm due to Zwick, resolving the natural open question raised in that work concerning the optimality of the approximation bound.

Given a $(1 - \eps)$ satisfiable instance of Max Horn-2SAT for some constant $\eps > 0$, it is possible to find a $(1 - 2\eps)$-satisfying assignment efficiently. This improves the algorithm given in \cite{KSTW} which finds a $(1 - 3\eps)$-satisfying assignment, and also matches the $(1 - c\eps)$ hardness for any $c$ smaller than 2 derived from vertex cover (under UGC).

Our hardness result is proved by constructing integrality gap instances for a semidefinite programming relaxation for the problems, and using Raghavendra's result to conclude that no algorithm can do better than the SDP assuming the UGC. The algorithmic result is based on rounding appropriate linear programming relaxations.

Joint work with Venkatesan Guruswami.