| Title | : | Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring |
| Speaker | : | Venkatesan Guruswamy (CMU, USA) |
| Details | : | Thu, 31 Jul, 2014 2:30 PM @ CS25 |
| Abstract: | : | 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 even 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. We might also briefly mention the general principle (based on the lack of certain polymorphisms) that underlies hardness of constraint satisfaction, and an improvement of the hypergraph coloring result (for 2k-uniform hypergraphs) ruling out coloring with any constant number of colors. Based on joint works with Per Austrin and Johan Håstad (http://eccc.hpi-web.de/report/2013/159/) and Euiwoong Lee (http://eccc.hpi-web.de/report/2014/043/) |
