## 4 Inapproximability of MEB and MBB
### Completeness
\[\Pr_{e\sim E_{H}}[e\subseteq T_{0}^{\prime}] \geqslant\sum_{j=1}^{k}\Pr_{e\sim E_{H}}[e\subseteq T_{0}^{\prime} \wedge j^{*}(A,x)=j] \tag{1}\] \[\geqslant\sum_{j=1}^{k}\Pr_{e\sim E_{H}}[e\subseteq T_{0}^{\prime }\wedge j^{*}(A,x)=j\wedge\
eg G_{1}\wedge\cdots\wedge\
eg G_{j-1}]\] \[=\sum_{j=1}^{k}\Pr_{e\sim E_{H}}[e\subseteq T_{0}^{\prime}\mid j^{ *}(A,x)=j\wedge\
eg G_{1}\wedge\cdots\wedge\
eg G_{j-1}]\Pr[j^{*}(A,x)=j\wedge \
eg G_{1}\wedge\cdots\wedge\
eg G_{j-1}]\] \[=(1-c_{3})\sum_{j=1}^{k}\Pr[j^{*}(A,x)=j\wedge\
eg G_{1}\wedge \cdots\wedge\
eg G_{j-1}]\] \[=(1-c_{3})\sum_{j=1}^{k}\Pr[j^{*}(A,x)=j]\Pr[-G_{1}\wedge\cdots \wedge\
eg G_{j-1}\mid j^{*}(A,x)=j].\]  
The probability that \(j^{*}(A,x)=j\) is in fact simply  
\[\Pr[j^{*}(A,x)=j]=\Pr[j^{*}(A,x)=j\mid j^{*}(A,x)>j-1]\prod_{q=1}^{j-1}\Pr[j^ {*}(A,x)\
eq q\mid j^{*}(A,x)>q-1]=c_{1}(1-c_{1})^{j-1}.\]  
Moreover, \(\Pr[\
eg G_{1}\wedge\cdots\wedge\
eg G_{j-1}\mid j^{*}(A,x)=j]\) can be written as  
\[\Pr[\
eg G_{1}\wedge\cdots\wedge\
eg G_{j-1}\mid j^{*}(A,x)=j]=\prod_{q=1}^{j -1}\Pr[\
eg G_{q}\mid j^{*}(A,x)=j\wedge\
eg G_{1}\wedge\cdots\wedge\
eg G_{q -1}]=(1-c_{2})^{j-1}.\]  
Plugging these two back into Equation (1), we have  
\[E_{H}(T_{0}^{\prime}) \geqslant(1-c_{3})\sum_{j=1}^{k}c_{1}(1-c_{1})^{j-1}(1-c_{2})^{j-1} \tag{2}\] Figure 2.0 Figure 2.1 Figure 2.2 Figure 2.3 Figure 2.4  
With Equation (2) in mind, we will proceed to bound \(c_{1},c_{2},c_{3}\). Before we do so, let us state two inequalities that will be useful: for every \(i\in[R]\), \(p\in[\ell]\), we have  
Figure 2.5  
and  
Figure 2.6  
The first inequality comes from the fact that, for \(\tilde{B}_{i}^{p}\) to be in \(S\) when \(A_{i}\
otin S\), at least one of the following events must occur: (1) \(A_{i}\
eq\tilde{A}_{i}^{p}\) and \(\tilde{A}_{i}^{p}\in S\), (2) \(B_{i}^{p}\
eq\tilde{B}_{i}^{p}\) and \(\tilde{B}_{i}^{p}\in S\), (3) \((\tilde{A}_{i}^{p},\tilde{B}_{i}^{p})\in(V\setminus S)\times S\). Each of first two occurs with probability \(\varepsilon_{\
u}\delta\) whereas the last event occurs with probability at most \(\eta\delta/(1-\delta)\leqslant 2\eta\delta\). On the other hand, for the second inequality, at least one of the following events must occur: (1) \(A_{i}\
eq\hat{A}_{i}^{p}\), (2) \(B_{i}^{p}\
eq\hat{B}_{i}^{p}\), (3) \((\tilde{A}_{i}^{p},\bar{B}_{i}^{p})\in S\times(V\setminus S)\). Each of first two occurs with probability \(\varepsilon_{V}\) whereas the last event occurs with probability at most \(\eta\). **Bounding \(c_{1}\). ** To compute \(c_{1}\), observe that \(\Pr[j^{*}(A,z)=j\mid j^{*}(A,z)>j-1]\) is the probability that, for exactly one \(i\) in the \(j\)-th block, \(A_{i}\in S\) and \(x_{i}\
eq\bot\). For a fixed \(i\), this happens with probability \(\beta\delta\). Hence, \(c_{1}=(R/k)\beta\delta(1-\beta\delta)^{R/k-1}\). Since \(\delta\in\left[\frac{k}{10\beta R},\frac{k}{\beta R}\right]\), we can conclude that \(c_{1}\) is simply a constant (i.e. \(c_{1}\in[10^{-5},0.5]\)). **Bounding \(c_{2}\). ** We next bound \(c_{2}\). If \(j^{*}(A,x)>j\), we know that \(|W(A,x,j)|\
eq 1\). Let us consider the following two cases:  
1. \(W(A,x,j)=\emptyset\). Observe that, if \(G_{j}\) occurs, then there exist \(p\in[\ell]\) and \(i\in\{R(j-1)/k+  
Let \(f:V^{R}\times\Omega^{R}\to\{0,1\}\) denote the indicator function for \(T\), i.e., \(f(A,x)=1\) if and only if \((A,x)\in T\). Note that \(\mathbb{E}_{A\sim V^{R},x\sim\Omega^{R}}f(A,x)=\mu_{H}(T)\leqslant 1/2\). Following notation from [11], we write \(f_{A}(x)\) as a shorthand for \(f(A,x)\). In addition, for each \(A\in V^{R}\), we will write \(\tilde{B}\sim\Gamma(A)\) as a shorthand for \(\tilde{B}\) generated randomly by sampling \(\tilde{A}\sim T_{V}(A)\), \(B\sim G^{\otimes R}(\tilde{A})\) and \(\tilde{B}\sim T_{V}(B)\) respectively. Let us restate [PERSON] et al. 's [11] lemma regarding the variance of \(\mathbb{E}_{x}f_{A}(x)\) in a more convenient formulation below. **Lemma 4** ([11] (Lemma 6.6)). : _For every \(A\in V^{R}\), let \(\mu_{A}\triangleq\mathbb{E}_{x\sim\Omega^{R}}f_{A}(x)\).