Unique games conjecture

This post was published way back in 2015 when this was in news. Mirroring it here from my old page.

Very recently, Subhash Khot won the Rolf Nevanlinna Prize, considered one of the top honours in the field of mathematics, for his contribution to computational complexity theory. The conjecture has broad applications in the theory of hardness of approximations and is unusual in the sense that unlike $\mathrm{P} = \mathrm{NP}$ problem, the academic world seems evenly divided on whether this conjecture is true or not.

“Some very natural, intrinsically interesting statements about things like voting and foams just popped out of studying the UGC… Even if the UGC turns out to be false, it has inspired a lot of interesting math research.”

—Ryan O’Donnell

This post is very basic and targeted towards anyone who has a knowledge of what complexity classes $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{NP}$-Hard and $\mathrm{NP}$-Complete means.

Assuming $\mathrm{P} \neq \mathrm{NP}$, researchers started exploring footholds for finding near optimal solutions efficiently. However, as it turns out, for some $\mathrm{NP}$-Complete optimization, it is not possible to approximate beyond a particular factor. Perhaps an example will highlight point.

Approximation Algorithms

Any $\mathrm{NP}$-optimization is either a minimization or a maximization problem. For a minimization problem, for each instance I, there exists a non-empty feasible set of solutions each of which is assigned an objective value. Our goal is to come up with the one whose objective value is lowest. Let’s call such a solution as optimal solution and let’s denote its value by $\mathrm{OPT}(I)$. We wish to come up with a solution which is as close (but greater since it is a minimization problem) as possible. Suppose, an approximation algorithm A outputs a solution which at most $\alpha$ times $\mathrm{OPT}(I)$ ($\alpha > 1$). We say that A is an $\alpha$-factor approximation algorithm. Similar results hold for maximization problems as well. We will now prove the hardness for TSP.

Example: Travelling Salesman Problem (TSP)

We will show that it is hard to approximate TSP for any approximation factor $\alpha$. To prove this, we will transform Hamiltonian Cycle Problem to TSP.

TSP: Given a weighted undirected graph, find the minimum weight tour that visits each vertex exactly once.

Hamiltonian Cycle Problem: Given a Graph G, does there exist a simple cycle that visits all the vertices of G exactly once?

Given an instance G of Hamiltonian Cycle Problem, construct an instance H of TSP as follows:

1. $V(H) = V(G)$.
2. H is a complete graph.
3. For all edges e in E(G), $w_e(H)=1$.
4. For other edges, $w_e(H) = \alpha n$ where $n = |V(G)|$.

If G has a hamiltonian cycle, $\mathrm{OPT}(H) = n$. Otherwise, the tour must include an edge of weight $\alpha n$. Hence, $\mathrm{OPT}(H) > \alpha n$.

If there is an $\alpha$-factor approximation factor for TSP, we can reduce Hamiltonian Cycle Problem to TSP and check the decidability of Hamiltonian Cycle Problem. If G has a hamiltonian cycle, $\mathrm{OPT}(H) = n$. Hence, the algorithm outputs a tour of weight at most $\alpha n$. Otherwise, $\mathrm{OPT}(H) > \alpha n$ which implies the tour the algorithm outputs has weight greater than $\alpha n$. This creates a gap between the YES/NO instances of Hamiltonian Cycle Problem and its decidability can be checked efficiently, which is not possible. Hence, it’s hard to approximate TSP to a factor of $\alpha$, for any $\alpha$.

Reduction

Let Pi be a minimization problem. A gap-introducing reduction maps an instance $\phi$ of SAT to an instance $x$ of Pi such that

• If $\phi$ is satisfiable, then $\mathrm{OPT}(x) \leq f(x)$, and
• If $\phi$ is not satisfiable, then $\mathrm{OPT}(x) > \alpha \cdot f(x)$.

Obviously, $\alpha \geq 1$. Such a kind of gap-introducing reduction immediately implies an inapproximability of $\alpha$ for Pi.

One problem with the above approach is blowing an “additive” gap to a “multiplicative” gap.

PCP Theorem

Probabilistic characterization of $\mathrm{NP}$ class yields a general technique for gap-introducing reduction. Informally speaking, a probabilistically checkable proof for an NP language is a proof whose validity can be checked probabilistically by examining its very few bits. A probabilistically checkable proof system comes with two parameters:

1. r(n): the number of random bits required by the verifier, and
2. q(n): the number of bits of the proof the verifier is allowed to examine.

A language L is in $\mathrm{PCP}(r(n),q(n))$ if there’s a verifier V that on input x, obtains a random string of length $c \cdot r(|x|)$ and queries $d \cdot q(|x|)$ bits of the proof such that (c & d are constants):

• If x is in L, then there’s a proof which verifier accepts with probability 1, and
• If x is not in L, then every proof is accepted with probability < 1/2.

The PCP Theorem gives another characterization of the class $\mathrm{NP}$.

PCP Theorem: $\mathrm{NP} = \mathrm{PCP}(\log n, 1)$

One direction of the proof, $\mathrm{NP} \subseteq \mathrm{PCP}(\log n, 1)$ is easy (try proving it as a small exercise). Other direction has been a result of years of research by various CS Theorists. For an excellent exposition to the history of PCP Theorem, refer this. Fortunately, the theorem, modulo its proof, is sufficient to derive hardness results.

Hardness of MAX-3SAT

In this example, we will try proving the hardness for MAX-3SAT. The reduction is from 3SAT. Specifically, there exists a constant $\alpha^*$ such that a 3SAT formula $\phi$ can be converted to a MAX-3SAT formula $\psi$ such that

• If $\phi$ is satisfiable, then $\mathrm{OPT}(\psi) = 1$, and
• If $\phi$ is not satisfiable, then $\mathrm{OPT}(\psi) < \alpha^*$.

The PCP for $\phi$ consists of a truth assignment to its boolean variables. The verifier uses $c \cdot \log(n)$ random bits and queries $q$ bits of the proof. In all, there can be $n^c$ different possible random strings generated and hence a total of $q \cdot n^c$ locations of the proof can be queried by the verifier. $\psi$ will have a variable corresponding to each of these locations.

A random string r picked by the verifier gives us a value either True or False based on the values of the variables in those $q$ locations. This truth value can be represented as a function $f_r$. Hence, we can define a 3SAT boolean formula $\psi_r$ as follows: for all $(v_1,...,v_q)$ such that $f(v_1,...,v_q) = 0$, add a clause. Then there can be at most $2^q$ clauses in $\psi_r$. Also, the length of each clause is $q$. Ensure that the length of each clause is 3 by adding $q-2$ new variables to each clause. The maximum number of clauses now is $q \cdot 2^q$.

$\psi$ is the conjunction of all $\psi_r$. $\psi$ has at most $n^c \cdot q \cdot 2^q$ clauses. If $\phi$ is satisfiable, all the clauses of $\psi$ are true. However, if $\phi$ is not satisfiable, at least half the random strings reject the proof i.e. at least half of $\psi_r$ are not satisfiable. Hence, the number of unsatisfiable clauses in $\psi$ must be at least $n^c / 2$. Hence, $\mathrm{OPT}(\psi) < 1 / (q \cdot 2^{q+1})$.

PCP Theorem was a landmark result in the field of computational complexity and after its inception, the focus moved on to produce optimal results i.e. to prove approximability and inapproximability results for a problem that match each other. The most influential development consisted of Label Cover problem (a.k.a. 2-Prover-1-Round Game), Raz’s Parallel Repetition Theorem, introduction of Long Code, its application in analyzing PCPs, and Hastad’s use of Fourier Series to analyze Long Code.

Label Cover Problem (a.k.a. 2-Prover-1-Round Game)

A 2-Prover-1-Round Game is a constraint satisfaction problem. It consists of a bipartite graph G(V,W,E) where vertices represent variables and edges represent constraints. Goal is to find a labelling $L: V \to [m], W \to [n]$ such that for all edges $e=(u,w)$ in E, the following “projection” constraint is satisfied: $\pi_e(L(u)) = L(w)$.

The game formulation: given an instance, consider a probabilistic verifier V which picks an edge $e=(v,w)$ in E at random and sends $v$ to Prover P1 and $w$ to Prover P2. The provers respond back with labels from set $[m]$ and $[n]$ respectively. The Verifier accepts only if $\pi_e(i) = j$ where $i$ and $j$ are the labels returned. The provers’ strategy is to maximize the probability of acceptance.

We are interested in the case when the label sets $[m]$ and $[n]$ have constant sizes. The PCP Theorem implies that the gap version is $\mathrm{NP}$-Hard and this gap can be amplified using Raz’s Parallel Repetition Theorem.

PCP Theorem + Raz’s Parallel Repetition Theorem

For every $\delta > 0$, the gap problem is $\mathrm{NP}$-Hard for instances with label cover of size $\mathrm{poly}(1/\delta)$. Many inapproximability results are obtained by reduction from this.

The inapproximability results derived from Unique Games often use gadgets constructed from Boolean hypercube. These reductions can be viewed as PCPs and the gadgets test, probabilistically, whether a given codeword is a Long Code or not. A useful Long Coding scheme is the so called dictatorship function on a boolean hypercube.

Unique Games Conjecture

The PCP strategy described above succeeds for some problems (MAX-3SAT, Clique, Hypergraph coloring), it doesn’t yield any useful results for problems such as Vertex Cover, MaxCut, Min-2SAT-Deletion and Graph coloring. For the first set of problems, PCPs are allowed to make three or more queries but for the second set of problems, at most two queries are allowed, which makes the PCP very weak.

It was pointed out that another barrier is the “many-to-one”-ness of the projection constraints in 2-Prover-1-Round Game. This motivated the study of Unique Games where $m=n$ and $\pi_e$ is a bijection.

Unique Game

A Unique Game is a constraint satisfaction problem: given a directed graph G(V,E) where vertices represent variables and edges represent constraint, the objective is to assign a label to each vertex from the set $[n]$ such that maximum number of edges are satisfied. The constraint on each edge $e$ is a bijection $\pi_e: [n] \to [n]$. An edge $e=(v,w)$ is satisfied by a labelling $L: V \to [n]$ if $\pi_e(L(v)) = L(w)$.

Note that if $\mathrm{OPT} = 1$, then such a labelling can be found in polynomial time: fixing the label of a vertex automatically fixes the label of every vertex which is its neighbour and so on. From the viewpoint of Unique Games Conjecture, the interesting case is when $\mathrm{OPT} = 1 - \epsilon$ where $\epsilon > 0$.

Unique Game Conjecture

Unique Games Conjecture: For every $\epsilon, \delta > 0$, there exists an $n = n(\epsilon, \delta)$, such that given a Unique Game instance, it is $\mathrm{NP}$-Hard to distinguish between the two cases:

• YES case: $\mathrm{OPT} \geq 1 - \epsilon$.
• NO case: $\mathrm{OPT} \leq \delta$.

Note that the conjecture is false if $\epsilon = 0$. Also, a random assignment satisfies $1/n$ fraction of edges and hence $n \geq 1/\delta$.