## 4 Inapproximability of MEB and MBB
### Preliminaries  
Before we continue, we need additional notations and preliminaries. For every graph \(G=(V,E,w)\) and every vertex \(v\), we write \(G(v)\) to denote the distribution on its neighbors weighted according to \(w\). (That is, \(\Pr_{v^{\prime}\sim G(v)}[u^{\prime}=u]\)is \(w((v,u))/d\) if \((v,u)\in E\) and is zero otherwise.) Moreover, we sometimes abuse the notation and write \(e\sim G\) to denote a random edge of \(G\) weighted according to \(w\).  
While our reduction can be understood without notation of unique games, it is best described in a context of unique games reductions. We provide a definition of unique games below.  
Definition 3 (Unique Game (UG)): A unique game instance \(\mathcal{U}=(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W}),[R],\{\pi_{ \epsilon}\}_{\epsilon\in\mathcal{E}})\) consists of an edge-weighted graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})\), a label set \([R]=\{1,\ldots,R\}\), and, for each \(e\in\mathcal{E}\), a permutation \(\pi_{e}:[R]\rightarrow[R]\). The goal is to find an assignment \(F:V\to[R]\) such that \(\operatorname{val}_{\mathcal{U}}(F)\triangleq\Pr_{(u,p)\sim\mathcal{G}}[\pi_{(u,p)}( F(u))=F(v)]\) is maximized; we call an edge \((u,v)\) such that \(\pi_{(u,p)}(F(u))=F(v)\)_satisfied.  
[PERSON]'s Unique Games Conjecture (UGC) [7] states that, for every \(\varepsilon>0\), it is NP-hard to distinguish between a unique game in which there exists an assignment satisfying at least \((1-\varepsilon)\) fraction of edges from one in which every assignment satisfies at most \(\varepsilon\) fraction of edges.  
Finally, we need some preliminaries in discrete Fourier analysis. We state here only few facts that we need. We refer interested readers to [55] for more details about the topic.  
For any discrete probability space \(\Omega\), \(f:\Omega^{R}\to[0,1]\) can be written as \(\sum_{\sigma\in|\Omega||^{R}}\hat{f}(\sigma)\phi_{\sigma}\) where \(\{\phi_{\sigma}\}_{\sigma\in[|\Omega||^{R}}\) is the product Fourier basis of \(L^{2}(\Omega^{R})\) (see [55] (Chapter 8.1)). The degree-\(d\) influence on the \(j\)-th coordinate of \(f\) is \(\inf_{j}^{d}(f)\triangleq\sum_{\sigma\in|\Omega||^{R},\sigma_{j}\
eq 1,\# \varepsilon\leq d}\hat{f}^{2}(\sigma)\) where \(\#\varepsilon\triangleq|\{i\in[R]\mid\sigma_{i}\
eq 1\}|\). It is well known that \(\sum_{j=1}^{R}\inf_{j}^{d}(f)\leqslant d\) (see [56] (Proposition 3.8)).  
We also need the following theorem. It follows easily from the so-called \"It Ain't Over Till It's Over\" conjecture, which is by now a theorem ([56] (Theorem 4.9)). For more details on how this version follows from there, please refer to [57] (p. 769).  
Theorem 4 ([56]): _For any \(\beta,\varepsilon_{T},\gamma>0\), there exists \(\kappa>0\) and \(t,d\in\mathbb{N}\) such that, if any functions \(f_{1},\ldots,f_{t}:\Omega^{R}\to\{0,1\}\) where \(\Omega\) is a probability space whose probability of each atom is at least \(\beta\) satisfy_  
\[\forall i\in[t],\ \operatorname*{\mathbb{E}}_{x\in\Omega^{R}}[f_{i}(x)] \leqslant 0.99\quad\text{ and }\quad\forall j\in[R],\forall 1\leqslant i_{1} \
eq i_{2}\leqslant t,\min\{\inf_{j}^{d}(f_{i_{1}}),\inf_{j}^{d}(f_{i_{2}})\} \leqslant\kappa,\]  
_then_  
\[\Pr_{x\in\Omega^{R},D\sim S_{\varepsilon_{T}}(R)}\left[\bigwedge_{i=1}^{t}f_{ i}(C_{D}(x))\equiv 1\right]<\gamma\]  
_where \(D\sim S_{\varepsilon_{T}}(R)\) is a random subset of \([R]\) where each \(i\in[R]\) is included independently w.p. \(\varepsilon_{T}\), \(C_{D}(x)\triangleq\{x^{\prime}\mid x^{\prime}_{[R]\setminus D}=x_{[R]\setminus D}\}\) and \(f_{i}(C_{D}(x))\equiv 1\) is a shorthand for \(\forall x^{\prime}\in C_{D}(x),f_{i}(x^{\prime})=1\)._  
We remark that the constant \(0.99\) in Theorem 4 could be replaced by any constant less than one; we use it only to avoid introducing more parameters