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.

The talk will sketch most of the proof, which is based on the fact that the only functions passing a natural dictatorship test are "juntas" depending on few variables. We will also briefly mention the general principle based on the lack of certain "polymorphisms" that underlies hardness of constraint satisfaction.

A strengthening of the k-SAT result shows that given a (2t+1)-uniform hypergraph admitting a balanced 2-coloring (at most t+1 vertices of each color in every hyperedge), it is NP-hard to even find a 2-coloring that avoids a monochromatic edge. This shows extreme hardness of discrepancy minimization for systems of bounded-size sets. [Subsequent work with Euiwoong Lee (http://eccc.hpi-web.de/report/2014/043/) in fact rules out coloring with any constant number of colors for the case of 2t-uniform hypergraphs with discrepancy 2.]