Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring

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/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/)