The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$

Introduction

In recent years, the theory of metric embeddings has played an increasing role in algorithm design. The best approximation algorithms for several NP-hard problems rely on techniques (and theorems) used to embed one metric space into another while preserving all pairwise distances up to a certain not too large factor, known as the distortion of the embedding.

Perhaps, the most well-known application of this paradigm is the SparsestCut problem. Given an $n$-vertex graph along with a set of demand pairs, one seeks to find a non-trivial partition of the graph that minimizes the sparsity, i.e., the ratio of the number of edges cut to the number of demand pairs cut. Strictly speaking, the problem thus defined is the non-uniform version of SparsestCut and in the absence of a qualification, we always mean the non-uniform version. In contrast, the uniform version refers to the special case when the set of demand pairs consists of all possible $\binom{n}{2}$ vertex pairs. In the uniform version, the sparsity is the same (up to a factor $2$ and a normalization factor of $n$) as the ratio of the number of edges cut to the size of the smaller side of the partition. A closely related problem is the BalancedEdge-Separator problem where one desires a partition that cuts a constant fraction of demand pairs and minimizes the number of the edges cut. In its uniform version, one desires a balanced partition, say a $(\nicefrac{{1}}{{3}},\nicefrac{{2}}{{3}})$-partition,In the uniform case, for a parameter $b\in(0,\nicefrac{{1}}{{2}}],$ a partition of the vertex set is said to be a $(b,1-b)$ partition if each side of the partition contains at least $b$ fraction of the vertices. that minimizes the number of the edges cut.

2 Our Contribution

Non-uniform BalancedEdge-Separator has an integrality gap of at least $(\log\log n)^{\nicefrac{{1}}{{6}}-\delta},$ where $\delta>0$ is an arbitrarily small constant. The integrality gap holds for a standard SDP relaxation with the triangle inequality constraints.

A surprising aspect of our integrality gap construction is that it proceeds via the Unique Games Conjecture (UGC) of Khot (see Section 3 for the statement of the conjecture). We first prove that the UGC implies a super-constant hardness result for non-uniform BalancedEdge-Separator.

Assuming the Unique Games Conjecture, non-uniform BalancedEdge-Separator is NP-hard to approximate within any constant factor.

The integrality gap instance for the UniqueGames SDP relaxation (see Figure 4) is stated below and is one of our main contributions. Here, we choose to provide an informal description of this construction (the reader should be able to understand this construction without even looking at the SDP relaxation).

For every edge $e\{u,v\}\in E$, the sets of vectors $B(u)$ and $B(v)$ are almost the same up to some small perturbation. To be precise, there is a permutation $\pi_{e}:[N]\mapsto[N],$ such that $\forall\ 1\leq i\leq N$, $\ \langle{u}_{\pi_{e}(i)},{v}_{i}\rangle\geq 1-\eta$. In other words, for every edge $(u,v)\in E$, the basis $B(u)$ moves smoothly/continuously to the basis $B(v)$.

For any labeling $\lambda:V\mapsto[N]$, i.e., assignment of an integer $\lambda(u)\in[N]$ to every $u\in V$, for at least $1-\nicefrac{{1}}{{N^{\eta}}}$ fraction of the edges $e\{u,v\}\in E$, we have $\lambda(u)\not=\pi_{e}(\lambda(v))$. In other words, no matter how we choose to assign a vector ${u}_{\lambda(u)}\in B(u)$ for every vertex $u\in V$, the movement from ${u}_{\lambda(u)}$ to ${v}_{\lambda(v)}$ is discontinuous for almost all edges $e\{u,v\}\in E$.

All vectors in $\cup_{u\in V}B(u)$ have coordinates in the set $\{\nicefrac{{1}}{{\sqrt{N}}},\nicefrac{{-1}}{{\sqrt{N}}}\}$ and, hence, any three of them satisfy the triangle inequality constraint.

This UniqueGames integrality gap instance construction is rather non-intuitive (at least to the authors when this paper was first written): One can walk on the graph $G$ by changing the basis $B(u)$ continuously, but as soon as one picks a representative vector for each basis, the motion becomes discontinuous almost everywhere. Of course, one can pick these representatives in a continuous fashion for any small enough local sub-graph of $G$, but there is no way to pick representatives in a global fashion.

Before we present a high-level overview of our proofs and discuss the difficulties involved, we give a brief overview of related and subsequent works since the publication of our paper in 2005.

3 Subsequent Works

For non-uniform BalancedEdge-Separator and, hence, non-uniform SparsestCut, our lower bound was improved to $\Omega(\log\log n)$ by Krauthgamer and Rabani and then to $(\log n)^{\Omega(1)}$ in a sequence of papers by Lee and Naor and Cheeger, Kleiner and Naor . For the uniform case, Devanur et al. obtained the first super-constant lower bound of $\Omega(\log\log n)$, thus, disproving the ARV conjecture as well. This latter bound has been recently improved to $2^{\Omega(\sqrt{\log\log n})}$ by Kane and Meka , building on the short code construction of Barak et al. . At a high level, the constructions in are in the same spirit as oursBoth and use a result of Kahn, Kalai and Linial instead of Bourgain (Theorem 2.14) as in our paper. whereas the constructions in are entirely different, based on the geometry of Heisenberg group.

In hindsight, our paper may be best viewed as a scheme that translates a UGC-based hardness result into an integrality gap for a SDP relaxation with triangle inequality constraints. In the conference version of our paper , we applied this scheme to the MaxCut and MinUncut problems as well. In particular, for MaxCut, we showed that the integrality gap for the Goemans and Williamson’s SDP relaxation remains unchanged even after adding triangle inequality constraints. Subsequent works of Raghavendra and Steurer and Khot and Saket cited above extend this paradigm in two directions: Firstly, their SDP solution satisfies additional constraints given by a super-constant number of rounds of the so-called Sherali-Adams LP hierarchy and secondly, they demonstrate that the paradigm holds for every constraint satisfaction problem (CSP). Since these two works already present more general results and in a more intuitive manner, we omit our results for MaxCut and MinUncut from this paper and keep the overall presentation cleaner by restricting only to SparsestCut.

Further, a result of Raghavendra shows that the integrality gap for a certain canonical SDP relaxation can be translated into a UGC-based hardness result with the same gap (this is a translation in the opposite direction as ours). Combined with the results in , one concludes that the integrality gap for the basic SDP relaxation remains unchanged even after adding a super-constant number of rounds of the Sherali-Adams LP relaxation. Finally, our techniques have inspired integrality gap for problems that are strictly speaking not CSPs, e.g., integrality gap for the QuadraticProgramming problem in and some new non-embeddability results, e.g., for the edit distance .

Rest of the Introduction

The overall construction can be divided into three steps:

A PCP reduction from UniqueGames to BalancedEdge-Separator.

Constructing an integrality gap instance for a natural SDP relaxation of UniqueGames.

We present an overview of each of these steps in three separate sections. Before we do that, let us summarize the precise notion of an integrality gap instance of BalancedEdge-Separator. To keep things simple in this exposition, we pretend as if our construction works for the uniform version of BalancedEdge-Separator as well. (Actually it does not; we have to work with the non-uniform version which complicates things a little.)

Given a graph $G^{\prime}(V^{\prime},E^{\prime})$, BalancedEdge-Separator asks for a $(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$-partition of $V^{\prime}$ that cuts as few edges as possible (however, the algorithm is allowed to output a roughly balanced partition, say $(\nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}})$-partition). We denote an edge $e$ between vertices $i,j$ by $e\{i,j\}.$ The SDP relaxation of BalancedEdge-Separator appears in Figure 1.

Note that a $\{+1,-1\}$-valued solution represents a true partition and, hence, this is an SDP relaxation. Constraint (4) is the triangle inequality constraint and Constraint (5) stipulates that the partition be balanced.Notice that if a set of vectors $\{v_{i}:i\in V^{\prime}\}$ is such that for every vector in the set, its antipode is also in the set, then constraint (5) is automatically satisfied. Our construction obeys this property. The notion of integrality gap is summarized in the following definition:

An integrality gap instance of BalancedEdge-Separator is a graph $G^{\prime}(V^{\prime},E^{\prime})$ and an assignment of unit vectors $i\mapsto{v}_{i}$ to its vertices such that:

Every balanced partition (say $(\nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}})$-partition, this choice is arbitrary) of $V^{\prime}$ cuts at least $\alpha$ fraction of edges.

The set of vectors $\{{v}_{i}|\ i\in V^{\prime}\}$ satisfy (3)-(5), and the SDP objective value in Equation (2) is at most $\gamma$.

The integrality gap is defined to be $\nicefrac{{\alpha}}{{\gamma}}$ (thus, we desire that $\gamma\ll\alpha$).

The PCP Reduction from Unique Games to Balanced Edge-Separator

An instance $\ {\mathcal{U}}=(G(V,E),[N],\{\pi_{e}\}_{e\in E})$ of UniqueGames consists of a graph $G(V,E)$ and permutations $\pi_{e}:[N]\mapsto[N]$ for every edge $e\{u,v\}\in E$. The goal is to find a labeling $\lambda:V\mapsto[N]$ that satisfies as many edges as possible. An edge $e\{u,v\}$ is satisfied if $\lambda(u)=\pi_{e}(\lambda(v))$. Let ${\rm opt}({\mathcal{U}})$ denote the maximum fraction of edges satisfied by any labeling.

UGC (Informal Statement): It is NP-hard to decide whether an instance ${\mathcal{U}}$ of UniqueGames has ${\rm opt}({\mathcal{U}})\geq 1-\eta$ (YES instance) or ${\rm opt}({\mathcal{U}})\leq\zeta$ (NO instance), where $\eta,\zeta>0$ can be made arbitrarily small by choosing $N$ to be a sufficiently large constant.

It is possible to construct an instance of BalancedEdge-Separator $G^{\prime}_{\varepsilon}(V^{\prime},E^{\prime})$ from an instance of UniqueGames. We describe only the high level idea here. The construction is parameterized by $\varepsilon>0$. The graph $G^{\prime}_{\varepsilon}$ has a block of $2^{N}$ vertices for every $u\in V$. This block contains one vertex for every point in the Boolean hypercube $\{-1,1\}^{N}$. Denote the set of these vertices by $V^{\prime}[u].$ More precisely,

We let $V^{\prime}\stackrel{{\scriptstyle\textup{def}}}{{=}}\cup_{u\in V}V^{\prime}[u]$. For every edge $e\{u,v\}\in E$, the graph $G^{\prime}_{\varepsilon}$ has edges between the blocks $V^{\prime}[u]$ and $V^{\prime}[v]$. These edges are supposed to capture the constraint that the labels of $u$ and $v$ are consistent, i.e., $\lambda(u)=\pi_{e}(\lambda(v))$. Roughly speaking, a vertex $(u,x)\in V^{\prime}[u]$ is connected to a vertex $(v,y)\in V^{\prime}[v]$ if and only if, after identifying the coordinates in $[N]$ via the permutation $\pi_{e}$, the Hamming distance between the bit-strings $x$ and $y$ is about $\varepsilon N$. This reduction has the following two properties:

(Completeness/YES case): If ${\rm opt}({\mathcal{U}})\geq 1-\eta$, then the graph $G^{\prime}_{\varepsilon}$ has a $(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$-partition that cuts at most $\eta+\varepsilon$ fraction of its edges.

(Soundness/NO Case): If ${\rm opt}({\mathcal{U}})\leq 2^{-O(\nicefrac{{1}}{{\varepsilon^{2}}})}$, then every $(\nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}})$-partition of $G^{\prime}_{\varepsilon}$ cuts at least $\sqrt{\varepsilon}$ fraction of its edges.

We were imprecise on two counts: (1) The soundness property holds only for those partitions that partition a constant fraction of the blocks $V^{\prime}[u]$ in a roughly balanced way. We call such partitions piecewise balanced. This is where the issue of uniform versus non-uniform version of BalancedEdge-Separator arises. (2) For the soundness property, we can only claim that every piecewise balanced partition cuts at least $\varepsilon^{t}$ fraction of edges, where any $t>\nicefrac{{1}}{{2}}$ can be chosen in advance. Instead, we write $\sqrt{\varepsilon}$ for the simplicity of notation.

Integrality Gap Instance for the Unique Games SDP Relaxation

This has already been described in Theorem 1.4. The graph $G(V,E)$ therein along with the orthonormal basis $B(u),$ for every $u\in V,$ can be used to construct an instance ${\mathcal{U}}=(G(V,E),[N],\{\pi_{e}\}_{e\in E})$ of UniqueGames. For every edge $e\{u,v\}\in E$, we have an (unambiguously defined) permutation $\pi_{e}:[N]\mapsto[N],$ where $\ \langle{u}_{\pi_{e}(i)},{v}_{i}\rangle\geq 1-\eta,$ for all $1\leq i\leq N$.

Thus, we have a concrete instance of UniqueGames with optimum at most $\nicefrac{{1}}{{N^{\eta}}}=o(1)$, and which has an SDP solution with objective value at least $1-\eta$. This is what an integrality gap example means: The SDP solution cheats in an unfair way.

Integrality Gap Instance for the Balanced Edge-Separator SDP Relaxation

Now we combine the two modules described above. We take the instance ${\mathcal{U}}=(G(V,E),[N],\{\pi_{e}\}_{e\in E})$ as above and run the PCP reduction on it. This gives us an instance $G^{\prime}(V^{\prime},E^{\prime})$ of BalancedEdge-Separator. We show that this is an integrality gap instance in the sense of Definition 1.5.

Since ${\mathcal{U}}$ is a NO instance of UniqueGames, i.e., ${\rm opt}({\mathcal{U}})=o(1)$, Theorem 1.6 implies that every (piecewise) balanced partition of $G^{\prime}$ must cut at least $\sqrt{\varepsilon}$ fraction of the edges. We need to have $\nicefrac{{1}}{{N^{\eta}}}\leq 2^{-O(\nicefrac{{1}}{{\varepsilon^{2}}})}$ for this to hold.

On the other hand, we can construct an SDP solution for the BalancedEdge-Separator instance which has an objective value of at most $O(\eta+\varepsilon)$. Note that a typical vertex of $G^{\prime}$ is $(u,x),$ where $u\in V$ and $x\in\{-1,1\}^{N}$. To this vertex, we attach the unit vector ${\mathbf{V}}_{u,x}^{\otimes t}$ (for $t=2^{240}+1$), where

This holds because whenever $((u,x),(v,y))$ is an edge of $G^{\prime}$, we have (after identifying the indices via the permutation $\pi_{e}:[N]\mapsto[N]$):

$\langle{u}_{\pi_{e}(i)},{v}_{i}\rangle\geq 1-\eta$ for all $1\leq i\leq N$ and

the Hamming distance between $x$ and $y$ is about $\varepsilon N$.

Quantitative Parameters

It follows from above discussion (see also Definition 1.5) that the integrality gap for BalancedEdge-Separator is $\Omega(\nicefrac{{1}}{{\sqrt{\varepsilon}}})$ provided that $\eta\approx\varepsilon$, and $N^{\eta}>2^{O(\nicefrac{{1}}{{\varepsilon^{2}}})}$. We can choose $\eta\approx\varepsilon\approx(\log N)^{\nicefrac{{-1}}{{3}}}$. Since the size of the graph $G^{\prime}$ is at most $n=2^{2N}$, we see that the integrality gap is $\approx(\log\log n)^{\nicefrac{{1}}{{6}}}$ as desired.

Proving the Triangle Inequality

Our proof of the triangle inequality constraints is essentially brute-force. As we mentioned before, more recent works obtain a more intuitive proof.

6 Organization of the Main Body of the Paper

In Section 2.1 we recall important definitions and results about metric spaces. Section 2.2 defines the cut optimization problems we are concerned about: SparsestCut and BalancedEdge-Separator. We also give their SDP relaxations for which we construct integrality gap instances. Section 2.5 presents useful tools from Fourier analysis.

In Section 3 we present the UGC and our integrality gap instance for an SDP relaxation of UniqueGames.

In Section 4 we present our PCP reduction from UniqueGames to BalancedEdge-Separator. The soundness proof this reduction is standard and appears in Appendix A.

We build on the UniqueGames integrality gap instance in Section 3 and the PCP reduction in Section 4 to obtain the integrality gap instance for BalancedEdge-Separator. This is presented in Section 5. This section has two parts: In the first part (Section 5.1) we present the graph and in the second part (Section 5.2) we present the corresponding SDP solution and prove its properties.

Appendix B is where we establish the main technical lemma needed to show that the SDP solutions we construct satisfy the triangle inequality constraint.

Preliminaries

We start with basics of metric embeddings. We are concerned with finite metric spaces which we denote by a pair $(X,d),$ where $X$ is the space and $d$ is the metric on its points. We say that a space $(X_{1},d_{1})$ embeds with distortion at most $\Gamma$ into another space $(X_{2},d_{2})$ if there exists a map $\phi:X_{1}\mapsto X_{2}$ such that for all $x,y\in X_{1}$

If $\ \Gamma=1,$ then $(X_{1},d_{1})$ is said to isometrically embed in $(X_{2},d_{2}).$

2 Balanced Edge-Separator, Sparsest Cut and their SDP Relaxations

In this section, we define the BalancedEdge-Separator and the SparsestCut problems and their SDP relaxations. All graphs are complete undirected graphs with non-negative weights or demands associated to its edges. For a graph $G(V,E)$ and $S\subseteq V$, let $E(S,\overline{S})$ denote the set of edges with one endpoint in $S$ and other in $\overline{S}$. A cut $(S,\overline{S})$ is called non-trivial if $S\not=\emptyset$ and $\overline{S}\not=\emptyset$.

The versions of SparsestCut and BalancedEdge-Separator that we define below are non-uniform versions with demands. The uniform version has all demands equal to $1,$ i.e., unit demand for every pair of vertices.

For a graph $G(V,E)$ with a weight ${\rm wt}(e)$ and a demand ${\rm dem}(e)$ associated to each edge $e\in E,$ the goal is to optimize

For a cut $(S,\overline{S})$, the ratio above is referred to as its sparsity.

The SDP relaxation for SparsestCut appears in Figure 2. We note that this is indeed a relaxation: Any cut $(S,\overline{S})$ corresponds to a feasible SDP solution by setting the vector ${v}_{x}$ to be ${v_{0}}$ or $-{v_{0}}$ depending on whether $x\in S$ or $x\in\overline{S}$ and ${v_{0}}$ is some fixed vector. The length of ${v_{0}}$ is chosen so as to satisfy the last SDP constraint. The SDP objective is then the same as the sparsity of the cut.

For a graph $G(V,E)$ with a weight ${\rm wt}(e),$ and a demand ${\rm dem}(e)$ associated to each edge $e\in E,$ let $D\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{e\in E}{\rm dem}(e)$ be the total demand. Let a balance parameter $B$ be given where $\nicefrac{{D}}{{6}}\leq B\leq\nicefrac{{D}}{{2}}$. The goal is to find a non-trivial cut $(S,\overline{S})$ that minimizes $\sum_{e\in E(S,\overline{S})}{\rm wt}(e),$ subject to $\sum_{e\in E(S,\overline{S})}{\rm dem}(e)\geq B.$ The cuts that satisfy $\sum_{e\in E(S,\overline{S})}{\rm dem}(e)\geq B$ are called $B$-balanced cuts.

The SDP relaxation for BalancedEdge-Separator appears in Figure 3. We note that this is indeed a relaxation: A $B$-balanced cut $(S,\overline{S})$ corresponds to a feasible SDP solution by setting the vector ${v}_{x}$ to be ${v_{0}}$ or $-{v_{0}}$ depending on whether $x\in S$ or $x\in\overline{S}$ and ${v_{0}}$ is a fixed unit vector.

An integrality gap instance for BalancedEdge-Separator is a concrete instance along with a feasible $B$-balanced SDP solution such that the SDP objective is at most $\gamma$ and the integral optimum over $\nicefrac{{B}}{{3}}$-balanced cuts is at least $\alpha$. The integrality gap is $\nicefrac{{\alpha}}{{\gamma}}$. Note that the SDP solution is $B$-balanced (in the sense of the last SDP constraint), but the integral optimum is allowed over $\nicefrac{{B}}{{3}}$-balanced cuts, i.e., over a larger class of cuts than the $B$-balanced cuts.

The integrality gap of the SparsestCut SDP relaxation is at most $f(n)$.

The integrality gap of the BalancedEdge-Separator SDP relaxation is at most $O(f(n))$.

Suppose $x\mapsto{v}_{x}$ is a solution for SDP of Figure 3 with objective value

Proof. The idea is that the good SDP solution as given implies the existence of a cut with low sparsity. If this cut already cuts $\Omega(B)$ of the demands, we are done. Otherwise the demands cut are erased (i.e., set to zero) and another sparse cut is found w.r.t. to the new (remaining) demands. This process is repeated until the sum of the demands cut in the sequence of cuts obtained so far is at least $\Omega(B)$. At this point, a random XOR of the cuts obtained so far yields a cut that cuts $\Omega(B)$ of the demands, but does not cut too much of the edge weight. Formally, we begin by observing that there is a cut $(S,\overline{S})$ with sparsity at most $f(n)\cdot\nicefrac{{\varepsilon}}{{B}}.$

If the cut $(S,\overline{S})$ happens to be $\nicefrac{{B}}{{3}}$-balanced, then we are done since the edge weight cut by it is at most the sparsity (which is at most $f(n)\cdot\nicefrac{{\varepsilon}}{{B}}$) times the demands cut (which is at most $D\leq 6B$). Otherwise the demands cut by $(S,\overline{S})$ is at most $\nicefrac{{B}}{{3}}$. We rename the cut as $(S_{1},\overline{S}_{1})$, set all the demands cut to zero, and repeat the process. This leads to a sequence of cuts $(S_{1},\overline{S}_{1}),\ldots,(S_{k},\overline{S}_{k})$. The process stops as soon as either

the cut just obtained cuts at least $\nicefrac{{B}}{{3}}$ of the demands or else

the sum of the demands cut over these $k$ cuts is at least $\nicefrac{{2B}}{{3}}$ (since a demand is set to zero as soon as it is cut, each original demand is counted at most once).

Note that prior to every step, at most $\nicefrac{{2B}}{{3}}$ of the (original) demands has been set to zero, so the SDP solution w.r.t. to the remaining demands still qualifies as being $B-\nicefrac{{2B}}{{3}}=\nicefrac{{B}}{{3}}$ balanced. Thus, at every step, the cut obtained has sparsity at most $f(n)\cdot\nicefrac{{\varepsilon}}{{(\nicefrac{{B}}{{3}})}}.$ We are done in the Case (a) as before and so we consider the Case (b).

To summarize, we have a sequence of cuts $(S_{1},\overline{S}_{1}),\ldots,(S_{k},\overline{S}_{k})$ such that the sum of the demands cut over these $k$ cuts is at least $\nicefrac{{2B}}{{3}}$. Moreover, the sparsity of each of these cuts is at most $O(f(n)\cdot\nicefrac{{\varepsilon}}{{B}})$ and, hence, the total edge weight cut by these cuts is at most $O(f(n)\varepsilon)$ (an edge is considered cut if it is cut by at least one of the $k$ cuts). Now we obtain our desired balanced partition by taking a random XOR of these cuts: The $i$-th cut is viewed as a $\{0,1\}$-valued function $\phi_{i}$ on the vertices and the desired cut is given by the function $\phi_{A}\stackrel{{\scriptstyle\textup{def}}}{{=}}\oplus_{i\in A}\phi_{i}$ where $A\subseteq[k]$ is a uniformly random subset. We show that for some choice of the set $A$, we get a cut $\phi_{A}$ that cuts at least $\nicefrac{{B}}{{3}}$ of the demands and at most $O(f(n)\varepsilon)$ of the edge weight. Clearly, the total edge weight cut is $O(f(n)\varepsilon)$ irrespective of the set $A$. On the other hand, each demand in the sum total of at least $\nicefrac{{2B}}{{3}}$ gets cut with probability $\nicefrac{{1}}{{2}}$ (this is the property of the random XOR). Thus, the expected demands cut by $\phi_{A}$ is at least $\nicefrac{{B}}{{3}}$ and this expectation is achieved for some choice of $A$.

The proof above shows that if the integrality gap for SparsestCut is upper bounded by $f(n)$ then the gap for BalancedEdge-Separator is bounded by $O(f(n))$. The same proof implicitly also shows that if there is an $f(n)$ approximation algorithm for SparsestCut, then the algorithm can be used iteratively a polynomial number of times to achieve $O(f(n))$ (pseudo-)approximation for BalancedEdge-Separator, see also [45, Chapter 7]. Given an instance of BalancedEdge-Separator that has a $B$-balanced cut that cuts an edge weight $\alpha$ and $B\geq\nicefrac{{D}}{{6}}$ where $D$ is the total demand, the algorithm finds a $\nicefrac{{B}}{{3}}$-balanced cut that cuts an edge weight $O(f(n)\alpha)$. In the contrapositive, a $g(n)$ hardness of approximation result for BalancedEdge-Separator implies an $\Omega(g(n))$ hardness result for SparsestCut.

4 Our Integrality Gap Instance for Balanced Edge-Separator

For $\ 0\leq\theta\leq 1$, a cut $A:V\mapsto\{-1,1\}$ is called $\theta$-piecewise balanced if

We also assign a unit vector to every vertex in the graph. Let ${v}_{x}$ denote the vector assigned to vertex $x$. Our construction of the graph $G(V,{\rm wt})$ and the vector assignment $x\mapsto{v}_{x}$ can be summarized as follows:

Fix any $\nicefrac{{1}}{{2}}<t<1$. For every sufficiently small $\varepsilon>0,$ there exists a graph $G(V,{\rm wt})$, with a partition $V=\cup_{i=1}^{r}V_{i}$, and a vector assignment $x\mapsto{v}_{x}$ for every $x\in V,$ such that

$|V|\leq 2^{2^{O(\nicefrac{{1}}{{\varepsilon^{3}}})}}$.

Every $\nicefrac{{5}}{{6}}$-piecewise balanced cut $A$ must cut $\varepsilon^{t}$ fraction of edges, i.e., for any such cut

The unit vectors $\{{v}_{x}\ |\ x\in V\}$ define a negative type metric, i.e., the following triangle inequality is satisfied:

For each part $V_{i}$, the vectors $\{{v}_{x}\ |\ x\in V_{i}\}$ are well-separated, i.e.,

The vector assignment gives a low SDP objective value, i.e.,

Construct an instance of BalancedEdge-Separator as follows. The graph $G(V,{\rm wt})$ is as in Theorem 2.9. The demands ${\rm dem}(e)$ depend on the partition $V=\cup_{i=1}^{r}V_{i}$. We let ${\rm dem}(e)=1$ if $e$ has both endpoints in the same part $V_{i}$ for some $1\leq i\leq r$ and ${\rm dem}(e)=0$ otherwise. Clearly, the total demand is $D\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{e}{\rm dem}(e)=r\cdot\binom{\nicefrac{{|V|}}{{r}}}{2}$.

Now, $x\mapsto{v}_{x}$ is an assignment of unit vectors that satisfy the triangle inequality constraints. This is a solution to the SDP of Figure 3. Property (4) of Theorem 2.9 guarantees that

Letting $B\stackrel{{\scriptstyle\textup{def}}}{{=}}\nicefrac{{D}}{{2}},$ the SDP solution is $B$-balanced and its objective value is at most $\varepsilon$. Using Lemma 2.6, we get a $B^{\prime}$-balanced cut $(A,\overline{A})$, $B^{\prime}\geq\nicefrac{{B}}{{3}}$ such that $\sum_{e\in E(A,\overline{A})}{\rm wt}(e)\leq O(\Gamma\cdot\varepsilon)$.

Claim: The cut $(A,\overline{A})$ must be a $\nicefrac{{5}}{{6}}$-piecewise balanced cut.

Proof of Claim. Let $p_{i}\stackrel{{\scriptstyle\textup{def}}}{{=}}{\Pr}_{x\in V_{i}}[A(x)=1].$ The total demand cut by $(A,\overline{A})$ is equal to $\sum_{i=1}^{r}p_{i}(1-p_{i})|V_{i}|^{2}$. This is at least $B^{\prime}\geq\nicefrac{{B}}{{3}}$ since $(A,\overline{A})$ is $B^{\prime}$-balanced. Hence,

Thus, $\sum_{i=1}^{r}p_{i}(1-p_{i})\geq\nicefrac{{r}}{{12}}.$ By Cauchy-Schwarz inequality,

Hence, $(A,\overline{A})$ must be a $\nicefrac{{5}}{{6}}$-piecewise balanced cut. However, Property (2) of Theorem 2.9 says that such a cut must cut at least $\varepsilon^{t}$ fraction of edges. This implies that $\Gamma=\Omega(\nicefrac{{1}}{{\varepsilon^{1-t}}})$. Theorem 1.2 now follows by noting that $t>\nicefrac{{1}}{{2}}$ is arbitrary and $n=|V|\leq 2^{2^{O(\nicefrac{{1}}{{\varepsilon^{3}}})}}$.

5 Fourier Analysis

For any $f:\{-1,1\}^{n}\mapsto\{-1,1\},$ $\sum_{S\subseteq[n]}\widehat{f}_{S}^{2}=1.$

The proof of this follows from the following sequence of equalities:

where the last equality follows from the orthonormality of the characters $\{\chi_{S}\}_{S\subseteq[n]}$ with respect to the inner product $\langle\cdot,\cdot\rangle_{2}.$

We also need to define the so-called Bonami-Beckner operator whose input is a Boolean function $f$ and whose output is again a Boolean function (which is supposed to be a smoothened version of $f$).

The following theorem shows that the Bonami-Beckner operator indeed smoothens $f$: It allows us to upper bound a higher norm of $T_{\rho}[f]$ of $f$ with a lower norm of $f$ under certain conditions.

for all $0\leq\rho\leq\left(\frac{p-1}{q-1}\right)^{\nicefrac{{1}}{{2}}}.$

The last set of preliminaries are important for the PCP reduction in Section 4.

The Long Code over a domain $[N]$ is indexed by all $x\in\{-1,1\}^{N}$. The Long Code $f$ of an element $j\in[N]$ is defined to be $f(x)\stackrel{{\scriptstyle\textup{def}}}{{=}}\chi_{\{j\}}(x)=x_{j},$ for all $x=(x_{1},\ldots,x_{N})\ \in\ \{-1,1\}^{N}.$

Thus, a Long Code is simply a Boolean function that is a dictatorship, i.e., it depends only on one coordinate. In particular, if $f$ is the Long Code of $j\in[N]$, then $\widehat{f}_{\{j\}}=1$ and all other Fourier coefficients are zero.

The following theorem (quantitatively) shows that if a Boolean function is such that its Fourier mass is concentrated on sets of small size, then it must be close to a junta. In other words, its Fourier mass on sets with small Fourier coefficients is small.

Fix any $\nicefrac{{1}}{{2}}<t<1$. Then, there exists a constant $c_{t}>0,$ such that, for all positive integers $k$, for all $\gamma>0$ and for all Boolean functions $f:\{-1,1\}^{n}\mapsto\{-1,1\},$

The Integrality Gap Instance for Unique Games

In this section, we present the integrality gap construction for a natural SDP relaxation of the UniqueGames problem. We start with defining the UniqueGames problem, the UGC of Khot along with the related preliminaries towards our construction.

The optimum opt$({\mathcal{U}})$ of the UniqueGames instance is defined to be the maximum weight of edges satisfied by any labeling:

We assume w.l.o.g that $\sum_{e\in E}{\rm wt}(e)=1$ so that the weights define a probability distribution over edges. A choice of a random edge refers to an edge chosen from this distribution. We also assume that the graph is regular in the sense that the sum of weights of edges incident on a vertex is the same for all vertices. A choice of a random edge incident on a vertex $v$ refers to a choice of a random edge conditional on having one endpoint as $v$.

For every pair of constants $\eta,\zeta>0$, there exists a sufficiently large constant $N=N(\eta,\zeta)$ such that given a UniqueGames instance $\;{\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right)$, it is NP-hard to distinguish whether:

Consider a UniqueGames instance ${\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right).$ Khot proposed the SDP relaxation in Figure 4 (inspired by a paper of Feige and Lovász ). Here, for every $v\in V,$ we associate a set of $N$ orthogonal vectors $\{{v}_{1},\ldots,{v}_{N}\}$. The intention is that if $i_{0}\in[N]$ is a label for vertex $v\in V$, then ${v}_{i_{0}}=\sqrt{N}{\bf 1},$ and ${v}_{i}={\bf 0}$ for all $i\not=i_{0}$. Here, ${\bf 1}$ is some fixed unit vector and ${\bf 0}$ is the zero-vector. However, once we take the SDP relaxation, this may no longer be true and $\{{v}_{1},{v}_{2},\ldots,{v}_{N}\}$ could be any set of orthogonal vectors.

The Noisy Hypercube and an Overview of the Integrality Gap Instance

The idea of the label extended graph and the implication that the small set expansion in the label extended graph implies low optimum for the UniqueGames instance were implicit in the conference version of this paper . We choose to make this more explicit here for the ease of presentation as well as in light of recent works that we briefly mention. Raghavendra and Steurer recently proposed the Small Set Expansion Conjecture and showed that it implies the UGC. The former states that for every constant $\varepsilon>0$, there exists a constant $\delta>0$ such that given an $n$-vertex graph that has a small non-expanding set, i.e., of size $\delta n$ and with edge expansion at most $\varepsilon$, it is NP-hard to find a set of size (roughly) $\delta n$ that is even somewhat non-expanding, i.e., with expansion at most $1-\varepsilon$. The SSE Conjecture has led to many interesting works including a new algorithm for UniqueGames by Arora, Barak and Steurer and the construction of the short code .

Given a UniqueGames instance ${\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right),$ the corresponding label extended graph $G^{\prime}(V^{\prime},E^{\prime},{\rm wt}^{\prime})$ is defined as follows:

$\forall e\{v,w\}\in E,i\in[N]$, we let $e^{\prime}\{(v,\pi_{e}(i)),(w,i)\}\in E^{\prime}$ and ${\rm wt}^{\prime}(e^{\prime})={\rm wt}(e)$.

Note that $\sum_{e^{\prime}\in E^{\prime}}{\rm wt}^{\prime}(e^{\prime})=N$.

It is helpful to view the label extended graph as being obtained from the UniqueGames graph by replacing every vertex $v$ by a group of $N$ vertices representing labels to $v$ and replacing every edge $e\{v,w\}$ by an edge-bundle of $N$ edges that form a perfect matching between the two groups and capture the bijective constraint $\pi_{e}$.

The expansion $\Phi(S^{\prime})$ of a set $S^{\prime}\subseteq V^{\prime}$ in the label extended graph is defined to be the probability of leaving $S^{\prime}$ when a random vertex in $S^{\prime}$ and then a random edge leaving that vertex (w.r.t. the weights ${\rm wt}^{\prime}$) is chosen. Note that $\Phi(S^{\prime})\in$. Any labeling $\lambda:V\mapsto[N]$ to a UniqueGames instance corresponds to the set $S^{\prime}_{\lambda}\subseteq V^{\prime}$ as follows:

An easy observation is that the (weighted) fraction of edges satisfied by a labeling $\lambda$ is related to the expansion of the set $S^{\prime}_{\lambda}$:

Here is a quick proof of the above equality. Pick a random vertex $(v,\lambda(v))$ in $S^{\prime}_{\lambda}$ by choosing a random vertex $v\in V$. Choosing a random edge incident on $(v,\lambda(v))$ (w.r.t. ${\rm wt}^{\prime}$) amounts to choosing a random edge $e\{v,w\}$ incident on $v$ (w.r.t. ${\rm wt}$) and outputting $\{(v,\lambda(v)),(w,\pi_{e}^{-1}(\lambda(v)))\}$. The expansion of $S^{\prime}_{\lambda}$ is now related to the event that $(w,\pi_{e}^{-1}(\lambda(v)))\in S^{\prime}_{\lambda}$ which is same as the event that $\pi_{e}^{-1}(\lambda(v))=\lambda(w)$ which is same as the event that $\lambda$ satisfies the edge $e\{v,w\}$.

As remarked before, our construction starts with the noisy hypercube graph and uses the fact that the graph is a small set expander. A natural way to describe this graph is by describing one step of the random walk on it (which then naturally leads to edge-weights with unit total weight).

The noisy hypercube graph $H$ with parameters $N$ and $0<\eta<\nicefrac{{1}}{{2}}$ has

the vertex set $\{-1,1\}^{N}$ with uniform distribution and

for any vertex ${x}\in\{-1,1\}^{N}$, choosing a random edge $({x},{y})$ incident on ${x}$ amounts to flipping every bit of ${x}$ with probability $\eta$ independently and letting ${y}$ to be the string so obtained.

Let $H$ be the noisy hypercube with parameters $N$ and $\eta$ and $S\subseteq\{-1,1\}^{N}$ be a set of relative size $\nicefrac{{1}}{{N}}$. Then $1-\Phi(S)\leq\nicefrac{{1}}{{N^{\eta+\eta^{2}}}}$.

Proof. Let $f:\{-1,1\}^{N}\mapsto\{0,1\}$ be the indicator function of the set $S$ so that $\|f\|_{p}^{p}=\nicefrac{{1}}{{N}}$ for any $1\leq p<\infty$. An application of Bonami-Beckner inequality gives (the probability is taken over choice of a random vertex ${x}$ and a random edge $({x},{y})$ incident on it)

Call an edge $({x},{y})$ of the noisy hypercube typical if the Hamming distance between ${x}$ and ${y}$ is close to $\eta N$, say between $\frac{\eta}{2}N$ and $2\eta N$. By the Chernoff bound, the (weighted) fraction of edges which are not typical is at most $2^{-\Omega(\eta N)}$ which is negligible in our context. We delete all these edges (mainly for the ease of presentation) and observe that the conclusion of Lemma 3.6 still holds with the bound $1-\Phi(S)\leq\nicefrac{{1}}{{N^{\eta}}}$. The weights of the edges change slightly, due to a re-normalization to preserve the unit total weight, but we ignore this issue.

We are now ready to construct an integrality gap instance for the SDP in Figure 4. To be precise, for parameters $N$ and $\eta$, we construct an instance ${\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right)$ of UniqueGames such that

(Soundness) ${\rm opt}({\mathcal{U}})\leq\nicefrac{{1}}{{N^{\eta}}}$ and

(Completeness) There is an SDP solution with objective value at least $1-9\eta$.

This construction is used later to construct integrality gap instances for cut problems. As mentioned earlier, the UniqueGames instance is constructed precisely so that the noisy hypercube graph happens to be its label extended graph and then the soundness guarantee follows from Lemma 3.6. The vertex set of the noisy hypercube graph is $\{-1,1\}^{N}$ where $N=2^{k}$. It is convenient for us to identify a point in $\{-1,1\}^{N}$ as a Boolean function $f:\{-1,1\}^{k}\mapsto\{-1,1\}$. We describe the construction formally now.

2 The Integrality Gap Instance

Let ${\mathcal{F}}$ denote the family of all Boolean functions on $\{-1,1\}^{k}.$ For $f,g\in{\mathcal{F}},$ define the product $fg$ as

Consider the equivalence relation $\equiv$ on ${\mathcal{F}}$ defined to be $f\equiv g$ if and only if there is an $S\subseteq[k],$ such that $f=g\chi_{S}$ (recall that $\chi_{S}$ is the Fourier character function). This relation partitions ${\mathcal{F}}$ into equivalence classes ${\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{m}$, each class containing exactly $N=2^{k}$ functions. We denote by $[{\mathcal{P}}_{i}]$ one arbitrarily chosen function in ${\mathcal{P}}_{i}$ as its representative. Thus, by definition,

It follows from the orthogonality of the characters $\{\chi_{S}\}_{S\subseteq[k]}$, that all the functions in any class are also mutually orthogonal. Further, for a function $f\in{\mathcal{F}},$ let ${\mathcal{P}}(f)$ denote the class ${\mathcal{P}}_{i}$ in which $f$ belongs.

Let ${\mu}\in_{\eta}{\mathcal{F}}$ denote a random perturbation function on $\{-1,1\}^{k}$ where for every $x\in\{-1,1\}^{k},$ independently, ${\mu}(x)=1$ with probability $1-\eta,$ and $-1$ with probability $\eta.$ Let $H$ be the noisy hypercube graph: It is a graph with vertex set ${\mathcal{F}}$ and for Boolean functions $f,g\in{\mathcal{F}},$ the weight of the edge $\{f,g\}$ is defined as follows:

where $h$ is a uniformly random function and ${\mu}$ is a random perturbation function. Note that the sum of weights over all (undirected) edges is $1$. Moreover, for any $S\subseteq[k],$ we have ${\rm wt}^{\prime}(\{f,g\})={\rm wt}^{\prime}(\{f\chi_{S},g\chi_{S}\}).$ We delete all edges $\{f,g\}$ such that the Hamming distance between $f$ and $g$ is outside the range $[\frac{\eta}{2}N,2\eta N]$ without really affecting anything as observed before.

The UniqueGames instance ${\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right)$ is now obtained by taking the noisy hypercube graph $H$ as above with a grouping of its vertices into classes ${\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{m}$. The edges of $H$ are grouped neatly into edge-bundles: A typical bundle is a set of $N$ edges between ${\mathcal{P}}_{i}$ and ${\mathcal{P}}_{j}$, all with the same weight, and forming a perfect matching between the $N$ vertices in each group. With this grouping in mind, the graph can now be naturally thought of as a label extended graph. The UniqueGames instance is obtained by thinking of each class ${\mathcal{P}}_{i}$ as a (super-)vertex, each function $f\in{\mathcal{P}}_{i}$ as a potential label to it, and the edge bundle between ${\mathcal{P}}_{i},{\mathcal{P}}_{j}$ as defining the bijective constraint between them. Here is a formal (somewhat tedious) description.

The UniqueGames graph $G(V,E)$ is defined as follows. The set of vertices is $V\stackrel{{\scriptstyle\textup{def}}}{{=}}\{{\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{m}\}$ as above. For every $f,g\in{\mathcal{F}}$ with Hamming distance in the range $[\frac{\eta}{2}N,2\eta N]$, there is an edge in $E$ between the vertices ${\mathcal{P}}(f)$ and ${\mathcal{P}}(g)$ with weight

(the factor of $N$ reflects the fact that there are $N$ pairs of functions that define the same edge). The set of labels for the UniqueGames instance is $2^{[k]}\stackrel{{\scriptstyle\textup{def}}}{{=}}\{S:S\subseteq[k]\}$, i.e., the set of labels $[N]$ is identified with the set $2^{[k]}$ (and by design $N=2^{k}$). Note that $f=[{\mathcal{P}}_{i}]\chi_{S}$ and $g=[{\mathcal{P}}_{j}]\chi_{T}$ for some sets $S,T\subseteq[k]$. The bijection $\pi_{e},$ for the edge $e\{{\mathcal{P}}_{i},{\mathcal{P}}_{j}\}$, can now be defined:

Here, $\star$ is the symmetric difference operator on sets. Note that $\pi_{e}:2^{[k]}\mapsto 2^{[k]}$ is a permutation on the set of allowed labels. An alternate view is that the potential labels to class ${\mathcal{P}}_{i}$ are really the functions in that class and for the edge defined by a pair $f\in{\mathcal{P}}_{i}$ and $g\in{\mathcal{P}}_{j}$ as above, $\pi_{e}$ designates $(f\chi_{U},g\chi_{U})$ as a matching pairs of labels for all $U\subseteq[k]$. We emphasize that every matching pair of labels corresponds to a pair of functions with Hamming distance in $[\frac{\eta}{2}N,2\eta N]$.

Soundness: No Good Labeling

Using Lemma 3.6 and Equation (15), i.e., the connection between the optimum of UniqueGames and the small set expansion of the label extended graph, it follows immediately that any labeling to the UniqueGames instance described above achieves an objective of at most $\nicefrac{{1}}{{N^{\eta}}}.$

Completeness: A Good SDP Solution

Recall that in the SDP relaxation of UniqueGames (Figure 4), for every vertex in $V,$ we need to assign a set of orthogonal vectors. For every vertex ${\mathcal{P}}_{i}\in V$, we choose a function $f\in{\mathcal{P}}_{i}$ arbitrarily, and with ${\mathcal{P}}_{i},$ we associate the set of vectors $\left\{{u}_{f\chi_{S}}^{\otimes 2}\right\}_{S\subseteq[k]}.$ The following facts are easily verified:

$\sum_{S\subseteq[k]}\left\langle{u}_{f\chi_{S}}^{\otimes 2},{u}_{f\chi_{S}}^{\otimes 2}\right\rangle=\sum_{S\subseteq[k]}\left\langle{u}_{f\chi_{S}},{u}_{f\chi_{S}}\right\rangle^{2}=N.$

For $S\neq T\subseteq[k],$ $\left\langle{u}_{f\chi_{S}}^{\otimes 2},{u}_{f\chi_{T}}^{\otimes 2}\right\rangle=\left\langle{u}_{f\chi_{S}},{u}_{f\chi_{T}}\right\rangle^{2}=\left\langle{u}_{\chi_{S}},{u}_{\chi_{T}}\right\rangle^{2}=0.$

For $f,g\in{\mathcal{F}}$ and $S,T\subseteq[k],$ $\left\langle{u}_{f\chi_{S}}^{\otimes 2},{u}_{g\chi_{T}}^{\otimes 2}\right\rangle=\left\langle{u}_{f\chi_{S}},{u}_{g\chi_{T}}\right\rangle^{2}\geq 0.$

For $f\in{\mathcal{P}}_{i},$ $g\in{\mathcal{P}}_{j}$ for $i\neq j,$

Hence, all the conditions (11)-(14) of the SDP are satisfied. Next, we show that this vector assignment has an objective at least $1-9\eta.$ Consider any UniqueGames edge defined by a pair $f,g$ with Hamming distance in the range $[\frac{\eta}{2}N,2\eta N]$. For any $S\subseteq[k]$, note that the same edge is defined by the pair $f\chi_{S},g\chi_{S}$ with the same Hamming distance and

Since the pairs $(f\chi_{S},g\chi_{S})$ are precisely the matching pairs of labels for the UniqueGames constraint, it follows that the objective of this SDP solution is at least $1-9\eta$ (accounting possibly for the non-typical pairs $f,g$ with Hamming distance outside of range $[\frac{\eta}{2}N,2\eta N]$ that were deleted and ignored throughout). Finally, note that since all the vectors have coordinates either $1$ or $-1$ (up to a normalization factor), any three vectors $u,v,w$ among those described above satisfy the triangle inequality:

Summarizing and Abstracting the Unique Games Instance

For any $0<\eta<\nicefrac{{1}}{{2}}$ and any integer $N$ that is a power of $2$, there is a UniqueGames instance ${\mathcal{U}}_{\eta}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right)$ along with a set of vectors $\{{v}_{i}^{\otimes 2}\}_{i\in[N]}$ for every vertex such that:

A PCP Reduction from Unique Games to Balanced Edge-Separator

This section presents the reduction from UniqueGames to non-uniform BalancedEdge-Separator which underlies the proof of Theorem 1.3. Remark 2.7 implies that if non-uniform BalancedEdge-Separator is hard to approximate within a factor of $C,$ then so is non-uniform SparsestCut up to a factor $\Omega(C)$. Hence, Theorem 1.3 can be strengthened as follows.

Assuming the UGC, it is NP-hard to approximate (non-uniform versions of) BalancedEdge-Separator and SparsestCut to within any constant factor.

We present the reduction and the proof of this theorem, modulo the soundness proof of the PCP reduction. The soundness proof is (by now) standard and relegated to Appendix A. The reduction underlying the proof of this theorem is used in the construction of the integrality gap for BalancedEdge-Separator presented in Section 5.

The reduction starts with a UniqueGames instance ${\mathcal{U}}=\left(G(V,E),[N],\{\pi_{e}\}_{e\in E},{\rm wt}\right)$. Each vertex $v\in V$ is replaced with a block of vertices $\{(v,x):x\in\{-1,1\}^{N}\}.$ The reduction has a parameter $\varepsilon$ which is to be thought of as a small constant. For each edge $e\{v,w\}$ in ${\mathcal{U}},$ a bundle of weighted edges are put between the two corresponding blocks of vertices taking into account the permutation $\pi_{e}$ corresponding to that edge. The weight of the edge between $(v,x)$ and $(w,y)$ is equal to the product of the weight of the edge $e\{v,w\}$ and the probability that, if we flip each bit of $x$ independently with probability $\varepsilon,$ we obtain $y\circ\pi_{e}.$ Here $y\circ\pi_{e}$ is the reordering of the coordinates of $y$ as dictated by $\pi_{e}$; formally, $(y\circ\pi_{e})_{i}=y_{\pi_{e}(i)}$ for all $i\in[N].$

Note that if we contract the vertices of the two hypercubes after identifying the coordinates according to $\pi_{e},$ we obtain exactly the noisy hypercube introduced in Definition 3.5. To complete the reduction, we need to specify the demand pairs. For reasons that will become clear in a bit, any pair of vertices in the same block is set to have demand one and the remaining pairs have demand zero.

Our reduction has the property that if the UniqueGames instance has a good labeling then there is a cut that cuts a constant fraction of the demand pairs and the weight of the edges crossing the cut is small. This is by construction: If the UniqueGames instance ${\mathcal{U}}$ has a good labeling, i.e., a $\lambda:V\mapsto[N]$ which satisfies at least a $1-\varepsilon$ fraction of the constraints of ${\mathcal{U}},$ then we consider the cut in the reduced graph whose one side consists of the vertices $(v,x)$ such that $x_{\lambda(v)}=1$ and the other side with vertices $(v,x)$ such that $x_{\lambda(v)}=-1.$ It is easy to see that the weight of the edges that cross this cut is $1-(1-\varepsilon)(1-\varepsilon)=O(\varepsilon).$ Moreover, the number of demand pairs cut is half that of the total demand pairs as the cut described above cuts each hypercube along a coordinate into two equal parts. This is the completeness of the reduction.

For soundness, we show that if every labeling of the UniqueGames instance satisfies a negligible (as a function of $\varepsilon$) fraction of the constraints, any cut in the reduced graph that cuts a constant fraction of demand pairs must have about $\sqrt{\varepsilon}\gg\varepsilon$ weight of edges crossing it. Since the reduction is local in the sense that it replaces each vertex in ${\mathcal{U}}$ by a set of vertices, and each edge in ${\mathcal{U}}$ by a bundle of edges between the corresponding sets, the weighted graph obtained by applying this reduction on ${\mathcal{U}}$ inherits connectivity properties of ${\mathcal{U}}.$ For instance, if ${\mathcal{U}}$ is disconnected, then there is a cut in the reduced graph which has no edges crossing it. Such a cut, however, puts each hypercube entirely on one side of the cut or the other, thus, cutting no demand pair. Hence, the way we have enforced demands essentially ensures that each cut in the reduced graph that cuts a constant fraction of demand pairs cuts most of the hypercubes into two roughly equal parts. Hence, for each vertex $v$ in ${\mathcal{U}}$ we can look at the restriction of this cut to the corresponding hypercube and assign to $v$ the label corresponding to the dimension of the hypercube which is the most correlated with the cut restricted to that hypercube. Since ${\mathcal{U}}$ does not have a good labeling, this strategy of converting a cut in the reduced graph to a labeling for ${\mathcal{U}}$ should not be good. Hence, one can deduce that, for any cut that cuts a constant fraction of the demand in the reduced graph, its restrictions to most hypercubes must not be well-correlated to any coordinate cut. This is where Bourgain’s Junta theorem (Theorem 2.14) comes in. It essentially implies that such a cut must be close to a majority cut in most hypercubes. This allows us to deduce that such a cut has at least $\sqrt{\varepsilon}$ weight edges crossing it, giving us the hardness of approximation ratio $\approx\nicefrac{{\sqrt{\varepsilon}}}{{\varepsilon}}$ which can be made larger than any constant by choosing $\varepsilon$ small enough.

We now describe the reduction formally. Here, it is instructive to break the reduction into two parts: The first consists of presenting a PCP verifier for UniqueGames and the second step involves translating the PCP verifier into a BalancedEdge-Separator instance. The completeness and the soundness of this verifier give us the proof of Theorem 4.1.

1 The PCP Verifier

For $\varepsilon\in(0,1),$ we present a PCP verifier which given a UniqueGames instance $\ {{\mathcal{U}}}=(G(V,E),[N],\{\pi_{e}\}_{e\in E})$ decides whether ${\rm opt}({\mathcal{U}})\sim 1$ or ${\rm opt}({\mathcal{U}})\sim 0.$ The verifier $V_{\varepsilon}$ expects, as a proof, the Long Code (see Definition 2.13) of the label of every vertex $v\in V.$ Formally, a proof $\Pi$ is $\{A^{v}\}_{v\in V},$ where each $A^{v}:\{-1,1\}^{N}\mapsto\{-1,1\}$ is the supposed Long Code of the label of $v.$ The actions of $V_{\varepsilon}$ on $\Pi$ are as follows.