About the small set expansion conjecture

Question

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \} }$) The ``small-set expansion conjecture" states that it is NP-Hard to determine if this is below $\epsilon$ or above $1-\epsilon$ for $\epsilon = 1/O(log(\frac{1}{\delta} ) )$

---

For context one notes that $h(G,\delta = \frac{1}{2})$ is the Cheeger constant which is known to be NP-hard to bound. But there does seem to exist values of $\delta$ (which ones?) for which $\phi(G,\delta)$ can be computed in polynomial time?

---

Towards understanding the small-set expansion conjecture one seems to prove this statement,

• If $W$ is the span of the Laplacian eigenvectors of $G$ such that their eigenvalues are less than some $\lambda \in [0,1]$ and if every $w \in W$ satisfies $\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ] )^2$ then for every set $S$ such that $\vert S \vert \leq \delta \vert V \vert$ we have $\phi(S) \geq \lambda(1 - \sqrt{C \delta} )$

[Reference, Lemma 8 here, http://www.boazbarak.org/sos/files/lec2d.pdf ]

---

My questions are,

• How does the above theorem help understand the conjecture stated at the beginning? What is the relationship between the two?

• Why should such vectors $w$ exists as demanded in the theorem? What is the intuition behind looking at such $w$?

• What is the intuition behind choosing that specific value of $\epsilon$ as in the statement of the conjecture?

Answer 1

I think the following should answer your questions, even though it's not exactly in the same order.

The original formulation of the small set expansion conjecture states that, analogously to the Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where there exists a $\delta$-sized set with expansion less than $\epsilon$ or it's the "NO" case where every $\delta$-sized set has expansion at least $1-\epsilon$. The paper of Raghavendra, Steuerer, and Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf showed that this is equivalent to the case where $\epsilon = O(\log (1/\delta))$ and in fact the case where in the NO case, for every $\delta' \geq \delta$, sets of size $\delta'$ have at least the same expansion as they would in the "$\epsilon$-noisy Gaussian graph" (see the paper for the precise statement). The reason for the relation $\epsilon = O(\log (1/\delta))$ is because this is the relation between those parameters in the Gaussian noise graph. This result of Raghavendra et al can be thought of as the small-set expansion analog for the paper of Khot, Kindler, Mossell and O'Donnell who showed a similar result for unique games, giving a very precise relation between the parameters $1/\delta$ (which in the unique games setting is known as the alphabet size) and $\epsilon$.

The result you mention discussed in my lecture notes is from Section 8 in my paper with Brandao, Harrow, Kelner, Steurer and Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). What we show there, roughly speaking, is that a graph is a small set expander if and only if the span of eigenvectors corresponding to low eigenvalues of its Laplacian does not contain an "analytically sparse" vector.

The intuition is the following: consider the following two extremes:

1) A random vector $w$. In this case, the distribution of entries of $w$ is approximately the Gaussian distribution, and so this satisfies that $\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$.

2) A vector $w$ that is the characteristic vector of a set of measure $\delta$ (i.e. it has $1$ in the coordinates belonging to the set, and $0$ in the others). In this case, $\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$.

Now, roughly speaking, the subspace $W$ corresponding to eigenvalues smaller than $\epsilon$ of the Laplacian corresponds to set which have expansion at most $\epsilon$ in the graph. So, if there exists a $\delta$-sized set with such expansion then there would be a vector $w$ (namely the projection of the characteristic vector of this set to $W$) with $\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$. The other direction (which is more challenging to prove but turns out to be true) is that if there is a vector $w$ with this property then we can also find a set with $o(1)$ measure with not too good expansion.