## 4 Inapproximability of MEB and MBB
### Bansal-Khot Long Code Test and A Candidate Reduction  
Theorem 4 leads us nicely to the Bansal-Khot long code test [58]. For UGC hardness reductions, one typically needs a _long code test_ (aka dictatorship gadget) which, on input \(f_{1},\ldots,f_{t}:\{0,1\}^{R}\to\{0,1\}\), has the following properties:  
* (Completeness) If \(f_{1}=\cdots=f_{t}\) is a long code, the test accepts with large probability. (A long code is simply \(j\)-junta (i.e. a function that depends only on the \(x_{j}\)) for some \(j\in[R]\).)
* (Soundness) If \(f_{1},\ldots,f_{t}\) are balanced (i.e. \(\operatorname*{\mathbb{E}}f_{1}=\cdots=\operatorname*{\mathbb{E}}f_{t}=1/2\)) and are \"far from being a long code\", then the test accepts with low probability. A widely-used notion of \"far from being a long code\", and one we will use here, is that the functions do not share a coordinate with large low degree influences, i.e., for every \(j\in[R]\) and every \(i_{1}\
eq i_{2}\in[t]\), at least one of \(\inf_{j}^{d}(f_{i_{1}})\) and \(\inf_{j}^{d}(f_{i_{2}})\) is small.  
Bansal-Khot long code test works by first picking \(x\sim\{0,1\}^{R}\) and \(D\sim S_{\varepsilon_{T}}(R)\). Then, test whether \(f_{i}\) evaluates to \(1\) on the whole \(C_{D}(x)\). This can be viewed as an \"algorithmic\" version of Theorem 4; specifically, the theorem (with \(\Omega=\{0,1\}\)) immediately implies the soundness property of this test. On the other hand, it is obvious that, if \(f_{1}=\cdots=f_{t}\) is a long code, then the test accepts with probability \(1/2-\varepsilon_{T}\).  
[PERSON] and [PERSON] used this test to prove tight hardness of approximation of Vertex Cover. The reduction is via a natural composition of the test with unique games. Their reduction also gives a cadidate reduction from UG to MUCHB, which is stated below in Figure 1.  
As is typical for gadget reductions, for \(T\subseteq V_{H}\), we view the indicator function \(f_{u}(x)\triangleq\mathds{1}[(u,x)\in T]\) for each \(u\in\mathcal{V}\) as the intended long code. If there exists an assignment \(\phi\) to the unique game instance that satisfies nearly all the constraints, then the bisection corresponding to \(f_{u}(x)=x_{\phi(u)}\) cuts only small fraction of edges, which yields the completeness of MUCHB.  
As for the soundness, we want to decode an UG assignment from \(T\subseteq V_{H}\) of size at most \(|V_{H}|/2\) which contains at least \(\varepsilon\) fraction of hyperedges. In terms of the tests, this corresponds to a collection of functions \(\{f_{u}\}_{u\in\mathcal{V}}\) such that \(\mathbb{E}_{u\sim\mathcal{V}}\,\mathbb{E}_{x\sim\{0,1\}^{R}}\,f_{u}(x)\leqslant 1/2\) and the Bansal-Khot test on \(f_{v_{1}},\ldots,f_{v_{t}}\) passes with probability at least \(\varepsilon\) where \(v_{1},\ldots,v_{t}\) are sampled as in Figure 1. Now, if we assume that \(\mathbb{E}_{x}\,f_{u}(x)\leqslant 0.99\) for all \(u\in\mathcal{V}\), then such decoding is possible via a similar method as in [58] since Theorem 4 can be applied here.  
Unfortunately, the assumption \(\mathbb{E}_{x}\,f_{u}(x)\leqslant 0.99\) does not hold for an arbitrary \(T\subseteq V_{H}\) and the soundness property indeed fails. For instance, imagine the constraint graph \(\mathcal{G}\) of the starting UG instance consisting of two disconnected components of equal size; let \(\mathcal{V}_{0}\), \(\mathcal{V}_{1}\) be the set of vertices in the two components. In this case, the bisection \((\mathcal{V}_{0}\times\{0,1\}^{R},\mathcal{V}_{1}\times\{0,1\}^{R})\) does not even cut a single edge! This is regardless of whether there exists an assignment to the UG that satisfies a large fraction of edges.