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

Speaker: Venkatesan Guruswami , 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

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL: http://www.ilyaraz.org/acseminar/

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Algorithms & Complexity Seminar: Venkatesan Guruswami

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

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Rebecca Yadegar Email at Friday, April 25, 2014 at 1:47 PM.