## 1 Introduction  
Since the PCP theorem was proved two decades ago [1; 2], our understanding of approximability of combinatorial optimization problems has grown enormously; tight inapproximability results have been obtained for fundamental problems such as Max-3 SAT [3], Max Clique [4] and Set Cover [5; 6]. Yet, for other problems, including Vertex Cover and Max Cut, known NP-hardness of approximation results come short of matching best known algorithms.  
[PERSON]'s introduction of the Unique Games Conjecture (UGC) [7] propelled another wave of development in hardness of approximation that saw many of these open problems resolved (see e.g., [8; 9]). Alas, some problems continue to elude even attempts at proving UGC-hardness of approximation. For a class of such problems, the failure stems from the fact that typical reductions are local in nature; many reductions from unique games to graph problems could produce disconnected graphs. If we try to use such reductions for problems that involve some forms of expansion of graphs (e.g., Sparsest Cut), we are out of luck.  
One approach to overcome the aforementioned issue is through the _Small Set Expansion Hypothesis_ (SSEH) of [PERSON] and [PERSON] [10]. To describe the hypothesis, let us introduce some notations. Throughout the paper, we represent an undirected edge-weighted graph \(G=(V,E,w)\) by a vertex set \(V\), an edge set \(E\) and a weight function \(w:E\rightarrow\mathbb{R}_{\geqslant 0}\). We call \(G\)_d-regular_ if \(\sum_{v:(u,v)\in E}w(u,v)=d\) for every \(u\in V\). For a \(d\)-regular weighted graph \(G\), the edge expansion \(\Phi(S)\) of \(S\subseteq V\) is defined as  
\[\Phi(S)=\frac{E(S,V\setminus S)}{d\min\{|S|,|V\setminus S|\}}\]where \(E(S,V\setminus S)\) is the total weight of edges across the cut \((S,V\setminus S)\). The small set expansion problem \(\operatorname{SSE}(\delta,\eta)\), where \(\eta,\delta\) are two parameters that lie in \((0,1)\), can be defined as follows.  
**Definition 1** (\(\operatorname{SSE}(\delta,\eta)\)).: _Given a regular edge-weighted graph \(G=(V,E,w)\), distinguish between:_  
* _(Completeness) There exists_ \(S\subseteq V\) _of size_ \(\delta|V|\) _such that_ \(\Phi(S)\leqslant\eta\)_._
* _(Soundness) For every_ \(S\subseteq V\) _of size_ \(\delta|V|\)_,_ \(\Phi(S)\geqslant 1-\eta\)_._  
Roughly speaking, SSEH asserts that it is NP-hard to distinguish between a graph that has a small non-expanding subset of vertices and one in which all small subsets of vertices have almost perfect edge expansion. More formally, the hypothesis can be stated as follows.  
**Conjecture 1** (Sseh [10]).: _For every \(\eta>0\), there is \(\delta=\delta(\eta)\in(0,1/2]\) such that \(\operatorname{SSE}(\delta,\eta)\) is NP-hard._  
Interestingly, SSEH not only implies UGC [10], but it is also equivalent to a strengthened version of the latter, in which the graph is required to have almost perfect small set expansion [11].  
Since its proposal, SSEH has been used as a starting point for inapproximability of many problems whose hardnesses are not known otherwise. Most relevant to us is the work of [PERSON], [PERSON] and [PERSON] (henceforth RST) [11] who devised a technique that exploited structures of SSE instances to avoid locality in reductions. In doing so, they obtained inapproximability of Minimum Bisection, Minimum Balanced Separator, and Minimum Linear Arrangement, all of which are not known to be hard to approximate under UGC.