## 4 Inapproximability of MEB and MBB
### RST Technique and The Reduction from SSE to MUCHB  
The issue described above is common for graph problems that involves some form of expansion of the graph. The RST technique [11] was in fact invented to specifically circumvent this issue. It works by first reducing SSE to UG and then exploiting the structure of the constructed UG instance when composing it with a long code test; this allows them to avoid extreme cases such as one above. There are four parameters in the reduction: \(\varepsilon_{V},\beta\in(0,1)\) and \(R,k\in\mathbb{N}\) such that \(R\) is divisible by \(k\). Before we describe the reduction, let us define additional notations:  
* Let \(G^{\otimes R}\) denote the \(R\)-tensor graph of \(G=(V,E,w)\); the vertex set of \(G^{\otimes R}\) is \(V^{R}\) and, for every \(A,B\in V^{R}\), the edge weight between \(A,B\) is the product of \(w(A_{i},B_{i})\) in \(G\) for all \(i\in[R]\). * For each \(A\in V^{R}\), \(T_{V}(A)\) denote the distribution on \(V^{R}\) where the \(i\)-th coordinate is set to \(A_{i}\) with probability \(1-\varepsilon_{V}\) and is uniformly randomly sampled from \(V\) otherwise. * Let \(\Pi_{R,k}\) denote the set of all permutations \(\pi^{\prime}\)s of \([R]\) such that, for each \(j\in[k]\), \(\pi(\{R(j-1)/k+1,\ldots,Rj/k\})=\{R(j-1)/k+1,\ldots,Rj/k\}\). * Let \(\{0,1,\bot\}_{\beta}\) denote the probability space such that the probability for \(0,1\) are both \(\beta/2\) and the probability for \(\bot\) is \(1-\beta\). The first step of reduction takes an \(\operatorname{SSE}(\delta,\eta,M)\) instance \(G=(V,E,w)\) and produces a unique game \(\mathcal{U}=(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W}),[R],\{\pi_{e} \}_{e\in E})\) where \(\mathcal{V}=V^{R}\) and the edges are distributed as follows:  
Figure 1: A Candidate Reduction from UG to MUCHB. 1. Sample \(A\sim V^{R}\) and \(\tilde{A}\sim T_{V}(A)\). 2. Sample \(B\sim G^{\otimes R}(\tilde{A})\) and \(\tilde{B}\sim T_{V}(B)\). 3. Sample two random \(\pi_{A},\pi_{B}\sim\Pi_{R,k}\). 4. Output an edge \(e=(\pi_{A}(\tilde{A}),\pi_{B}(\tilde{B}))\) with \(\pi_{(A,B)}=\pi_{B}\circ\pi_{A}^{-1}\). Here \(\varepsilon_{V}\) is a small constant, \(k\) is large and \(R/k\) should be think of as \(\Theta(1/\delta)\). When there exists a set \(S\subseteq V\) of size \(\delta|V|\) with small edge expansion, the intended assignment is to, for each \(A\in V^{R}\), find the first block \(j\in[k]\) such that \(|A(j)\cap S|=1\) where \(A(j)\) denotes the multiset \(\{A_{R(j-1)/k+1},\dots,A_{Rj/k}\}\) and let \(F(A)\) be the coordinate of the vertex in that intersection. If no such \(j\) exists, we assign \(F(A)\) arbitrarily. Note that, since \(R/k=\Theta(1/\delta)\), \(\Pr[|A(j)\cap S|=1]\) is constant, which means that only \(2^{-\Omega(k)}\) fraction of vertices are assigned arbitrarily. Moreover, it is not hard to see that, for the other vertices, their assignments rarely violate constraints as \(\varepsilon_{V}\) and \(\Phi(S)\) are small. This yields the completeness. In addition, the soundness was shown in [10; 11], i.e., if every \(S\subseteq V\) of size \(\delta|V|\) has near perfect expansion, no assignment satisfies many constraints in \(\mathcal{U}\) (see Lemma 7). The second step is to reduce this \(\mathrm{UG}\) instance to a hypergraph \(H=(V_{H},E_{H})\). Instead of making the vertex set \(V^{R}\times\{0,1\}^{R}\) as in the previous candidate reduction, we will instead make \(V_{H}=V^{R}\times\Omega^{R}\) where \(\Omega=\{0,1,\bot\}_{\beta}\) and \(\beta\) is a small constant. This does not seem to make much sense from the \(\mathrm{UG}\) reduction standpoint because we typically want to assign which side of the bisection \((A,x)\in V_{H}\) is according to \(x_{F(A)}\) but \(x_{F(A)}\) could be \(\bot\) in this construction. However, it makes sense when we view this as a reduction from SSE directly: let us discard all coordinates \(i\)'s such that \(x_{i}=\bot\) and define \(A(j,x)\triangleq\{A_{i}\mid i\in\{R(j-1)/k+1,\dots,Rj/k\}\wedge x_{i}\
eq\bot\}\).