## 4 Inapproximability of MEB and MBB
### Completeness
#### 4.5.1 Decoding an Unique Games Assignment  
With Lemma 5 ready, we can now decode an UG assignment via a similar technique from [58]. **Lemma 6**. : _For any \(\varepsilon_{T},\gamma,\beta>0\), let \(t=t(\varepsilon_{T},\gamma,\beta),\kappa=\kappa(\varepsilon_{T},\gamma,\beta)\) and \(d=d(\varepsilon_{T},\gamma,\beta)\) be as in Theorem 4. For any integer \(\ell\geqslant 100t\), if there exists \(T\subseteq V_{H}\) of such that \(\mu_{H}(T)\leqslant 1/2\) and \(E_{H}(T)\geqslant 2\gamma+10\beta+2^{-\ell/100}\), then there exists \(F:V^{R}\to[R]\) such that_  
\[\Pr_{A\sim V^{R},\tilde{B}\sim\Gamma(A),\pi_{A},\pi_{B}\sim\Pi_{R,k}}[\pi_{A}^ {-1}(F(\pi_{A}(\tilde{A})))=\pi_{B}^{-1}(F(\pi_{B}(\tilde{B})))]\geqslant \frac{\gamma\kappa^{2}}{4d^{2}\ell^{2}}.\]  
**Proof. ** The decoding procedure is as follows. For each \(A\in V^{R}\), we construct a set of candidate labels \(\text{\rm Cand}[A]\triangleq\{j\in[R]\mid\text{\rm inf}_{j}^{d}(f_{A})\geqslant\kappa\}\). We generate \(F\) randomly by, with probability \(1/2\), setting \(F(A)\) to be a random element of \(\text{\rm Cand}[A]\) and, with probability \(1/2\), sampling \(\tilde{B}\sim\Gamma(A)\) and setting \(F(A)\) to be a random element from \(\text{\rm Cand}[B]\). Note that, if the candidate set is empty, then we simply pick an arbitrary assignment. From our assumption that \(T\) is \(\Pi_{R,k}\)-invariant, it follows that, for every \(A\in V^{R},\pi\in\Pi_{R,k}\) and \(j\in[R]\), \(\Pr_{F}[\pi^{-1}(F(\pi(A)))=j]=\Pr_{F}[F(A)=j]\). In other words, we have  
\[\Pr_{F,A\sim V^{R},\tilde{B}\sim\Gamma(A),\pi_{A},\pi_{B}\sim\Pi_{R,k}}[\pi_{ 1}^{-1}(F(\pi_{A}(\tilde{A})))=\pi_{B}^{-1}(F(\pi_{B}(\tilde{B})))]=\Pr_{F,A \sim V^{R},\tilde{B}\sim\Gamma(A)}[F(\tilde{A})=F(\tilde{B})]. \tag{12}\]  
Next, note that, from how our reduction is defined, \(E_{H}(T)\) can be written as  
\[E_{H}(T)=\Pr_{A\sim V^{R},\tilde{B}^{1},\ldots,\tilde{B}^{\ell}\sim\Gamma(A), x\sim\Omega^{R},D\sim S_{\epsilon_{T}}(R)}\left[\bigwedge_{i=1}^{\ell}f_{ \tilde{B}i}(C_{D}(x))\equiv 1\right].\]  
From \(E_{H}(T)\geqslant 2\gamma+10\beta+2^{-\ell/100}\) and from Lemma 5, we can conclude that  
\[\Pr_{A,\tilde{B}^{1},\ldots,\tilde{B}^{\ell},x,D}\left[\left(\bigwedge_{i=1}^{ \ell}f_{\tilde{B}i}(C_{D}(x))\equiv 1\right)\wedge\left(\left|\{i\in[\ell]\mid\mu_{ \tilde{B}^{i}}\leqslant 0.99\}\right|\geqslant t\right)\right]\geqslant 2\gamma.\]  
From [PERSON]'s inequality, we have  
\[\gamma \leqslant\Pr_{A,\tilde{B}^{1},\ldots,\tilde{B}^{\ell}}\left[\Pr_ {x,D}\left[\left(\bigwedge_{i=1}^{\ell}f_{\tilde{B}i}(C_{D}(x))\equiv 1\right) \wedge\left(\left|\{i\in[\ell]\mid\mu_{\tilde{B}^{i}}\leqslant 0.99\}\right| \geqslant t\right)\right]\geqslant\gamma\right]\] \[=\Pr_{A,\tilde{B}^{1},\ldots,\tilde{B}^{\ell}}\left[\left(\Pr_{x, D}\left[\bigwedge_{i=1}^{\ell}f_{\tilde{B}i}(C_{D}(x))\equiv 1\right]\geqslant\gamma \right)\wedge\left(\left|\{i\in[\ell]\mid\mu_{\tilde{B}^{i}}\leqslant 0.99\} \right|\geqslant t\right)\right].\]  
A tuple \((A,\tilde{B}^{1},\ldots,\tilde{B}^{\ell})\) is said to be _good_ if \(\Pr_{x\sim\Omega^{R},D\sim S_{\epsilon_{T}}(R)}\left[\bigwedge_{i=1}^{\ell}f_ {\tilde{B}i}(C_{D}(x))\equiv 1\right]\geqslant\gamma\) and \(\left|\{i\in[\ell]\mid\mu_{\tilde{B}^{i}}\leqslant 0.99\}\right|\geqslant t\). For such tuple, Theorem 4 implies that there exist \(i_{1}\
eq i_{2}\in[\ell],j\in[R]\) s.t. \(\text{\rm inf}_{j}^{d}(f_{\tilde{B}^{1}}),\text{\rm inf}_{j}^{d}(f_{\tilde{B} ^{2}})\geqslant\kappa\). This means that \(\text{\rm Cand}(\tilde{B}^{i_{1}})\cap\text{\rm Cand}(\tilde{B}^{i_{2}})\
eq\emptyset\). Hence, if we sample a tuple \((A,\tilde{B}^{1},\ldots,\tilde{B}^{\ell})\) at random, and then sample two different \(\tilde{B},\tilde{B}^{\prime}\) randomly from \(\tilde{B}^{1},\ldots,\tilde{B}^{\ell}\), then the tuple is good with probability at least \(\gamma\) and, with probability \(1/\ell^{2}\), we have \(\tilde{B}=\tilde{B}^{i_{1}},\tilde{B}^{\prime}=\tilde{B}^{i_{2}}\).