[Colloquium] THEORY TALK TODAY: Yuan Zhou
Katie Casey
caseyk at cs.uchicago.edu
Tue May 25 08:32:01 CDT 2010
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date: Tuesday, May 25, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street
----------------------------------------------------------
Speaker: Yuan Zhou
From: Carnegie Mellon University and TTI-C
Web: http://www.cs.cmu.edu/~yuanzhou/
Title: Tight Bounds on the Approximability of Almost-satisfiable Horn SAT
Abstract: 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~\cite{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 < 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~\cite{prasad-stoc08} 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100525/67d2573f/attachment.htm
More information about the Colloquium
mailing list