An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Ene et al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation.

We show that for every positive ε > 0, unless NP ⊂ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2 log 1-ε n by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is, in fact, 1 - ε versus ε hard assuming the Unique Games Conjecture. Then, we present an O (√n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms.

In a beautiful result, Raghavendra established optimal Unique Games Conjecture (UGC)-based inapproximability for a large class of constraint satisfaction problems (CSPs). In the class of CSPs he considers, of which Maximum Cut is a prominent example, the goal is to find an assignment which maximizes a weighted fraction of constraints satisfied. He gave a generic semi-definite program (SDP) for this class of problems and showed how the approximability of each problem is determined by the corresponding SDP (upto an arbitrarily small additive error) assuming the UGC. He noted that his techniques do no apply to CSPs with strict constraints (all of which must be satisfied) such as Vertex Cover. In this paper we address the approximability of these strict-CSPs. In the class of CSPs we consider, one is given a set of constraints over a set of variables, and a cost function over the assignments, the goal is to find an assignment to the variables of minimum cost which satisfies all the constraints. We present a generic linear program (LP) for a large class of strict-CSPs and give a systematic way to convert integrality gaps for this LP into UGC-based inapproximability results. Some important problems whose approximability our framework captures are Vertex Cover, Hypergraph Vertex Cover, k-partite-Hypergraph Vertex Cover, Independent Set and other covering and packing problems over q-ary alphabets, and a scheduling problem. For the covering and packing problems, which occur quite commonly in practice as well, we provide a matching rounding algorithm, thus settling their approximability upto an arbitrarily small additive error.

We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) where each constraint has constant arity is approximation resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining a $\rho'$ approximation for any $\rho'>\rho$ is UG-hard. For the simplest OCSP, the Maximum Acyclic Subgraph (MAS) problem, this implies that obtaining a $\rho$-approximation for any constant $\rho>1/2$ is UG-hard. Specifically, for every constant $\varepsilon>0$ the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction $(1-\varepsilon)$ of its edges, it is UG-hard to find one with more than $(1/2+\varepsilon)$ of its edges. Note that it is trivial to find an acyclic subgraph with $1/2$ the edges by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied, and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset $\Pi\subseteq S_k$ of permutations on $\{1,2,\dots,k\}$. An instance of such an OCSP is a set V and a collection of constraints, each of which is an ordered k-tuple of V. The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in $\Pi$. A random ordering of V is expected to satisfy a $\rho=\frac{|\Pi|}{k!}$ fraction. We show that, for any fixed k, it is hard to obtain a $\rho'$-approximation for $\Pi$-OCSP for any $\rho'>\rho$. The result is in fact stronger: we show that for every $\Lambda\subseteq\Pi\subseteq S_k$, and an arbitrarily small $\varepsilon$, it is hard to distinguish instances where a $(1-\varepsilon)$ fraction of the constraints can be ordered according to $\Lambda$ from instances where at most a $(\rho+\varepsilon)$ fraction can be ordered as in $\Pi$. A special case of our result is that the Betweenness problem is hard to approximate beyond a factor $1/3$. The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation.

A permutation constraint satisfaction problem (permCSP) of arity k is specified by a subset LambdasubeSkof permutations on {1,2,...,k}. An instance of such a permCSP consists of a set of variables V and a collection of constraints each of which is an ordered k-tuple of V. The objective is to find a global ordering sigma of the variables that maximizes the number of constraint tuples whose ordering (under sigma) follows a permutation in Lambda. This is just the natural extension of constraint satisfaction problems over finite domains (such as Boolean CSPs) to the world of ordering problems. The simplest permCSP corresponds to the case when Lambda consists of the identity permutation on two variables. This is just the maximum acyclic subgraph (MAS) problem. It was recently shown that the MAS problem is unique-games hard to approximate within a factor better than the trivial 1/2 achieved by a random ordering. Building on this work, in this paper we show that for *every* permCSP of arity 3, beating the random ordering is unique-games hard. The result is in fact stronger: we show that for every LambdasubePisube S3, given an instance of permCSP(Lambda) that is almost-satisfiable, it is hard to find an ordering that satisfies more than Pi/6 +epsiv of the constraints even under the relaxed constraint Pi (for arbitrary epsiv> 0). A special case of our result is that the *Betweenness* problem is hard to approximate beyond a factor 1/3. Interestingly, for *satisfiable* instances of Betweenness, a factor 1/2 approximation algorithm is known. Thus, every permutation CSP of arity up to 3 resists approximation beyond the trivial random ordering threshold. In contrast, for Boolean CSPs, there are both approximation resistant and non-trivially approximable CSPs of arity 3.

We prove that approximating the max. acyclic subgraph problem within a factor better than 1/2 is unique games hard. Specifically, for every constant epsiv > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsiv) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + epsiv) of its edges, then the UGC is false. Note that it is trivial to find an acyclic subgraph with 1/2 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The existence of a rho-approximation algorithmfor rho > 1/2 has been a basic open problem for a while. Our result is the first tight inapproximability result for an ordering problem. The starting point of our reduction isa directed acyclic subgraph (DAG) in which every cut isnearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed by Charikar et al. Using this, we are able to study max. acyclic subgraph, which is a constraint satisfaction problem (CSP) over an unbounded domain, by relating it to a proxy CSP over a bounded domain. The latter is then amenable to powerful techniques based on the invariance principle. Our results also give a super-constant factor inapproximability result for the feedback arc set problem. Using our reductions, we also obtain SDP integrality gapsfor both the problems.

The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGC-based hardness results. We show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. Specifically, we convert linear programming integrality gaps for the Multiway Cut, 0-Extension, and and Metric Labeling problems into UGC-based hardness results. Qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthmover linear program) yields the best possible approximation. Taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthmover linear program. Prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming.