## 4 Inapproximability of MEB and MBB
### RST Technique and The Reduction from SSE to MUCHB
If there exists a block \(j\in[k]\) such that \(|A(j,x)\cap S|=1\), then let \(j^{*}(A,x)\) be the first such block (i.e. \(\min\{j\mid|A(j,x)\cap S|=1\}\)), let \(i^{*}(A,x)\) be the coordinate in the intersection between \(A(j^{*}(A,x),x)\) and \(S\), and assign \((A,x)\) to \(T_{x^{*}(A,x)}\). (Recall that \((T_{0},T_{1})\) is the intended bisection.) Otherwise, if no such block exists, assign \((A,x)\) arbitrarily. Observe that, in the intended solution, the side that \((A,x)\) is assigned to does not change if (1) \(A_{i}\) is modified for some \(i\in[R]\) s.t. \(x_{i}=\bot\) or (2) we apply some permutation \(\pi\in\Pi_{R,k}\) to both \(A\) and \(x\). In other words, we can \"merge\" two vertices \((A,x)\) and \((A^{\prime},x^{\prime})\) that are equivalent through these changes together in the reduction. For notational convenience, instead of merging vertices, we will just modify the reduction so that, if \((A,x)\) is included in some hyperedge, then every \((A^{\prime},x^{\prime})\) reachable from \((A,x)\) by these operations is also included in the hyperedge. More specifically, if we define \(M_{x}(A)\triangleq\{A^{\prime}\in V^{R}\mid A^{\prime}_{i}=A_{i}\text{ for all }i\in[R]\text{ such that }x_{i}\
eq\bot\}\) corresponding to the first operation, then we add \(\pi(A^{\prime},x)\) to the hyperedge for every \(A^{\prime}\in M_{x}(A)\) and \(\pi\in\Pi_{R,k}\). The full reduction is shown in Figure 2.  
Note that the test we apply here is slightly different from Bansal-Khot test as our test is on \(\Omega=\{0,1,\bot\}_{\beta}\) instead of \(\{0,1\}\) used in [58]. Another thing to note is that now our vertices and hyperedges are weighted, the vertices according to the product measure of \(V^{R}\times\Omega^{R}\) and the edges according to the distribution produced from the reduction. We write \(\mu_{H}\) to denote the measure on the  
Figure 2: Reduction from SSE to Max UnCut Hypergraph Bisection. vertices, i.e., for \(T\subseteq V^{R}\times\{0,1,\bot\}^{R}\), \(\mu_{H}(T)=\Pr_{A\sim V^{R},x\sim\Omega^{R}}[(A,x)\in T]\), and we abuse the notation \(E_{H}(T)\) and use it to denote the probability that a hyperedge as generated in Figure 2 lies completely in \(T\). We note here that, while the MUCHB as stated in Lemma 1 is unweighted, it is not hard to see that we can go from weighted version to unweighted by copying each vertex and each edge proportional to their weights. (Note that this is doable since we can pick \(\beta,\varepsilon_{V},\varepsilon_{T}\) to be rational.) The advantage of this reduction is that the vertex \"merging\" makes gadget reduction non-local; for instance, it is clear that even if the starting graph \(V\) has two connected components, the resulting hypergraph is now connected. In fact, [PERSON] et al. (2011) show a much stronger quantitative bound. To state this, let us consider any \(T\in V_{H}\) with \(\mu_{H}(T)=1/2\). From how the hyperedges are defined, we can assume w.l.o.g. that, if \((A,x)\in T\), then \(\pi(A^{\prime},x)\in T\) for every \(A^{\prime}\in M_{x}(A)\) and every \(\pi\in\Pi_{R,k}\). Again, let \(f_{A}(x)\triangleq\mathbb{1}[(A,x)\in T]\). The following bound on the variance of \(\mathbb{E}_{x}f_{A}(x)\) is implied by the proof of Lemma 6.6 in ([PERSON] et al., 2011):  
\[\mathop{\mathbb{E}}_{A\sim V^{R}}\left(\mathop{\mathbb{E}}_{x\sim\Omega^{R}}f_ {A}(x)-1/2\right)^{2}\leqslant\beta.\]  
The above bound implies that, for most \(A\)'s, the mean of \(f_{A}\) cannot be too large. This will indeed allow us to ultimately apply Theorem 4 on a certain fraction of the tuples \((\bar{B}^{1},\ldots,\bar{B}^{\ell})\) in the reduction, which leads to an UG assignment with non-negligible value.