[Colloquium] Talk by Yuan Zhou, CMU and TTIC on May 25, 2010

[Katie Casey]

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/20100514/cbe66f02/attachment.htm