Talk: Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring
, Carnegie Mellon University
Date: Wednesday, April 30, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, email@example.com
Relevant URL: http://www.ilyaraz.org/acseminar/
Speaker URL: None
TALK: Algorithms & Complexity Seminar: Venkatesan Guruswami
Given a k-SAT instance with the promise that there is an assignment satisfying at least t out of k literals in each clause, can one efficiently find a satisfying assignment (setting at least one literal to true in every clause)? The NP-hardness of 3-SAT implies that this problem is NP-hard when t <= k/3, and extensions of some 2-SAT algorithms give efficient solutions when t >= k/2.
We prove that for t < k/2, the problem is NP-hard. Thus, satisfiability becomes hard when the promised density of true literals falls below 1/2. One might thus say that the transition from easy to hard in 2-SAT vs. 3-SAT takes place just after two and not just before three.
A strengthening of this result shows that given a (2k+1)-uniform hypergraph that can be 2-colored such that each edge has near-perfect balance (at most k+1 vertices of each color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. This shows extreme hardness of discrepancy minimization for systems of bounded-size sets.
The talk will sketch our proof of the SAT result, which is based on the fact that the only functions passing a natural ``dictatorship test" are ``juntas" depending on few variables. Time permitting, we might also mention the general principle underlying hardness of promise CSPs based on lack of weak polymorphisms of large arities, and an improvement of the hypergraph coloring result (for 2k-uniform hypergraphs) ruling out coloring with any constant number of colors.
Based on joint work with Per Austrin and Johan Hastad (http://eccc.hpi-web.de/report/2013/159/) and Euiwoong Lee (http://eccc.hpi-web.de/report/2014/043/)
Created by Rebecca Yadegar at Friday, April 25, 2014 at 1:47 PM.