## 4 Inapproximability of MEB and MBB
### Completeness  
In the completeness case, we define a bisection similar to that described above. This bisection indeed cuts only a small fraction of hyperedges; quantitatively, this yields the following lemma. **Lemma 3**. : _If there is a set \(S\subseteq V\) such that \(\Phi(S)\leqslant\eta\) and \(|S|=\delta|V|\) where \(\delta\in\left[\frac{k}{10\beta R},\frac{k}{\beta R}\right]\), then there is a bisection \((T_{0},T_{1})\) of \(V_{H}\) such that \(E_{H}(T_{0}),E_{H}(T_{1})\geqslant 1/2-O(\varepsilon_{T}/\beta)-O(\eta\ell/ \beta)-O(\varepsilon_{V}\ell/\beta)-2^{-\Omega(k)}\) where \(O(\cdot)\) and \(\Omega(\cdot)\) hide only absolute constants._  
Proof. : Suppose that there exists \(S\subseteq V\) of size \(|S|=\delta|V|\) where \(\left[\frac{k}{10\beta R},\frac{k}{\beta R}\right]\) and \(\Phi(S)\leqslant\eta\). For \(A\in V^{R},x\in\{0,1,\bot\}^{R}\), we will use the following notations throughout this proof:  
* For \(j\in[k]\), let \(W(A,x,j)\) denote the set of all coordinates \(i\) in \(j\)-th block such that \(x_{i}\
eq\bot\) and \(A_{i}\in S\), i.e., \(W(A,x,j)=\{i\in\{R(j-1)/k+1,\ldots,kj/k\}\mid A_{i}\in S\wedge x_{i}\
eq\bot\}\). * Let \(j^{*}(A,x)\) denote the first block \(j\) with \(|W(A,x,j)|=1\), i.e., \(j^{*}(A,x)=\min\{j\in[k]\mid|W(A,x,j)|=1\}\). Note that if such block does not exist, we set \(j^{*}(A,x)=-1\). * Let \(i^{*}(A,x)\) be the only element in \(W(A,x,j^{*}(A,x))\). If \(j^{*}(A,x)=-1\), let \(i^{*}(A,x)=-1\). To define \(T_{0}\), \(T_{1}\), we start by constructing \(T_{0}^{\prime}\subseteq T_{0}\) and \(T_{1}^{\prime}\subseteq T_{1}\) as follows: assign each \((A,x)\in V_{H}\) such that \(j^{*}(A,x)\
eq-1\) to \(T_{x_{i^{*}(A,x)}}\). Finally, we assign the rest of the vertices arbitrarily to \(T_{0}\) and \(T_{1}\) in such a way that \(\mu_{H}(T_{0})=\mu_{H}(T_{1})\). Since \(T_{0}^{\prime}\subseteq T_{0}\), \(T_{1}^{\prime}\subseteq T_{1}\), it suffices to show the desired bound for \(E_{H}(T_{0}^{\prime}),E_{H}(T_{1}^{\prime})\). Due to symmetry, it suffices to bound \(E_{H}(T_{0}^{\prime})\). Recall that \(E_{H}(T_{0}^{\prime})=\Pr[e\subseteq T_{0}^{\prime}]\) where \(e\) is generated as detailed in Figure 2.  
To compute \(E_{H}(T_{0}^{\prime})\), it will be most convenient to make a block-by-block analysis. In particular, for each block \(j\in[k]\), we define \(G_{j}\) to denote the event that \(j^{*}(B^{\prime},x^{\prime})=j\) for some \((B^{\prime},x^{\prime})\in e\). We will be interested in bounding the following conditional probabilities:  
* \(c_{1}\triangleq\Pr[j^{*}(A,x)=j\mid j^{*}(A,x)>j-1]\)
* \(c_{2}\triangleq\Pr[G_{j}\mid j^{*}(A,x)>j\wedge\
eg G_{1}\wedge\cdots\wedge \
eg G_{j-1}]\)
* \(c_{3}\triangleq\Pr[e\
subseteq T_{0}^{\prime}\mid j^{*}(A,x)=j\wedge\
eg G_{1 }\wedge\cdots\wedge\
eg G_{j-1}]\)  
Here and throughout the proof, \(e,A,\bar{A}^{1},\ldots,\bar{A}^{\ell},B^{1},\ldots,B^{\ell},\bar{B}^{1}, \ldots,\bar{B}^{\ell}\) are as sampled by our reduction in Figure 2. Note also that it is clear that \(c_{1},c_{2},c_{3}\) do not depend on \(j\). Before we bound \(c_{1},c_{2},c_{3}\), let us see how these probabilities can be used to bound \(E_{H}(T_{0}^{\prime})\).