## Appendix C Comparison Between SSEH and Strong UGC  
In this section, we briefly discuss the similarities and differences between the classical Unique Games Conjecture [7], the Small Set Expansion Hypothesis [10] and the Strong Unique GamesConjecture [58]. Let us start by stating the Unique Games Conjecture, proposed by [PERSON] in his influential work [7]:  
**Conjecture A1** (Unique Games Conjecture (UGC) [7]). : _For every \(\varepsilon,\eta>0\), there exists \(R=R(\varepsilon,\eta)\) such that, given an UG instance \((\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W}),[R],\{\tau_{\varepsilon} \}_{\varepsilon\in\mathcal{E}})\) such that \(\mathcal{G}\) is regular, it is NP-hard to distinguish between the following two cases:_  
* _(Completeness) There exists an assignment_ \(F:\mathcal{V}\to[R]\) _such that_ \(\operatorname{val}_{\mathcal{U}}(F)\geqslant 1-\varepsilon\)_._
* _(Soundness) For every assignment_ \(F:\mathcal{V}\to[R]\)_,_ \(\operatorname{val}_{\mathcal{U}}(F)\leqslant\eta\)_._  
In other words, [PERSON]'s UGC states that it is NP-hard to distinguish between an UG instance which is almost satisfiable from one in which only small fraction of edges can be satisfied. While SSEH as stated in Conjecture 1 is not directly a statement about an UG instance, it has a strong connection with the UGC. [PERSON] and [PERSON] [10], in the same work in which they proposed the conjecture, observed that SSEH is implied by a variant of UGC in which the soundness is strengthened so that the constraint graph is also required to be a small-set expander (i.e. every small set has near perfect edge expansion). In a subsequent work, [PERSON], [PERSON] and [PERSON] [11] showed that the two conjectures are in fact equivalent. More formally, the following variant of UGC is equivalent to SSEH:  
**Conjecture A2** (UGC with Small-Set Expansion (UGC with SSE) [10]). : _For every \(\varepsilon,\eta>0\), there exist \(\delta=\delta(\varepsilon)>0\) and \(R=R(\varepsilon,\eta)\) such that, given an UG instance \((\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W}),[R],\{\tau_{\varepsilon} \}_{\varepsilon\in\mathcal{E}})\) such that \(\mathcal{G}\) is regular, it is NP-hard to distinguish between the following two cases:_  
* _(Completeness) There exists an assignment_ \(F:\mathcal{V}\to[R]\) _such that_ \(\operatorname{val}_{\mathcal{U}}(F)\geqslant 1-\varepsilon\)_._
* _(Soundness) For every assignment_ \(F:\mathcal{V}\to[R]\)_,_ \(\operatorname{val}_{\mathcal{U}}(F)\leqslant\eta\)_. Moreover,_ \(\mathcal{G}\) _satisfies_ \(\Phi(S)\geqslant 1-\varepsilon\) _for every_ \(S\subseteq\mathcal{V}\) _of size_ \(\delta n\)_._  
While our result is based on SSEH (which is equivalent to UGC with SSE), [PERSON] et al. [22] relies on another strengthened version of the UGC, which requires the following additional properties:  
* There is not only an assignment that satisfies almost all constraints, but also a partial assignment to almost the whole graph such that every constraint between two assigned vertices is satisfied. * The graph in the soundness case has to satisfy the following vertex expansion property: for every not too small subset of \(\mathcal{V}\), its neighborhood spans almost the whole graph. More formally, the conjecture can be stated as follows. **Conjecture A3** (Strong UGC (SUGC) [58]).