Abstract: Given a 5-SAT instance admitting an assignment satisfying at least 2 literals in each clause, can one efficiently find a satisfying assignment that sets at least one literal to true in each clause? Given a 5-uniform hypergraph admitting a red-blue coloring of its vertices with exactly two red vertices in each hyperedge, can one efficiently find a red-blue coloring that leaves no hyperedge monochromatic? Given a graph admitting a homomorphism to the 7-cycle, can one efficiently 3-color it?
The answers to these questions are: No (unless P=NP), yes, and open respectively. These are examples of *promise* constraint satisfaction problems (PCSP), where in the decision version, we need to distinguish instances satisfiable according to one set of predicates, from those that are unsatisfiable even under relaxed versions of those predicates. PCSPs generalize normal CSPs where the two sets of predicates are identical. The (recently resolved) famous dichotomy conjecture states that every CSP is either polytime decidable or NP-hard. Further, the tractable cases are precisely those admitting closure operations (called “polymorphisms”) that preserve the predicates defining the CSP.
The landscape of PCSPs reveals several new phenomena and challenges on both the algorithmic and hardness fronts compared to the CSP world. This talk will describe some of our forays into better understanding PCSPs, which revolve around the notion of “weak polymorphisms.” We will sketch our hardness proof (with P. Austrin and J. Håstad) for the above promise k-SAT problem, based on a characterization of the weak polymorphisms as juntas. We will discuss a body of work (with J. Brakensiek) that develops the weak polymorphism framework to prove new hardness results for graph coloring and establish a complexity dichotomy for the case of Boolean symmetric PCSP. Numerous intriguing problems about PCSPs and the state of polymorphisms remain open, and we will mention a couple of them.