We prove NP-hardness of approximating the Unique-Games problem, and the special cases: Max-Cut, Max-2-LIN. Our result is the present best inapproximability for all these problems, in the regime of interest. The proof involves an improved gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, no such reduction can establish an inapproximability surpassing a factor $C > 2.54$. Previously, no such limitations on gadget reductions was known.

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NP-hard approximation factors of $14/15+\epsilon$ and $1/2+\epsilon$. An OCSP is said to be approximation resistant if it is hard to approximate it better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-$m$ approximation-resistant OCSPs accepting only a fraction $1 / (m/2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to the assumption $P \ne NP$.

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language on an arbitrary finite domain. Using an 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 for such problems.

In this paper, we explain why the simple LP-based rounding algorithm for the Vertex Cover problem is optimal assuming the UGC. Complementing Raghavendra's result, our result generalizes to a class of strict, covering/packing type CSPs. We first write down a natural LP relaxation for this class of problems and present a simple rounding algorithm for it. The key ingredient, then, is a dictatorship test, which is parametrized by a rounding-gap example for this LP, whose completeness and soundness are the LP-value and the rounded value respectively.

We prove that every permutation CSP of constant arity, k, is approximation resistant.

We show that for every positive epsilon, unless NP has randomized polynomial time algorithms, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-\varepsilon} n}$ by a reduction from the maximum label cover problem. Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

Maximum Acyclic Subgraph is the problem of identifying the largest subset of edges in a directed graph that do not contain a directed cycle. We prove that approximating the Maximum Acyclic Subgraph problem within a factor better than $1/2$ is Unique-Games hard. Our results also give a super-constant factor inapproximability result for the Feedback Arc Set problem. Using our reductions, we also obtain SDP integrality gaps for both the problems.

We show that for $k$-way multicut, $0$-extension and metric labeling problems, a simple linear programming relaxation (known as the earthmover relaxation) provides the best approximation (upto an arbitrarily small additive error) to the optimum of a given instance of the above mentioned problems, assuming the UGC.

In this paper we focus on estimating the amount of information that can be embedded in the sequencing of packets in ordered channels.

We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements.