  We develop a new approach for approximating large independent sets when the
input graph is a one-sided spectral expander - that is, the uniform random walk
matrix of the graph has the second eigenvalue bounded away from 1.
Consequently, we obtain a polynomial time algorithm to find linear-sized
independent sets in one-sided expanders that are almost $3$-colorable or are
promised to contain an independent set of size $(1/2-\epsilon)n$. Our second
result above can be refined to require only a weaker vertex expansion property
with an efficient certificate. Somewhat surprisingly, we observe that the
analogous task of finding a linear-sized independent set in almost
$4$-colorable one-sided expanders (even when the second eigenvalue is $o_n(1)$)
is NP-hard, assuming the Unique Games Conjecture.
  All prior algorithms that beat the worst-case guarantees for this problem
rely on bottom eigenspace enumeration techniques (following the classical
spectral methods of Alon and Kahale) and require two-sided expansion, meaning a
bounded number of negative eigenvalues of magnitude $\Omega(1)$. Such
techniques naturally extend to almost $k$-colorable graphs for any constant
$k$, in contrast to analogous guarantees on one-sided expanders, which are
Unique Games-hard to achieve for $k \geq 4$.
  Our rounding builds on the method of simulating multiple samples from a
pseudodistribution introduced by Barak et. al. for rounding Unique Games
instances. The key to our analysis is a new clustering property of large
independent sets in expanding graphs - every large independent set has a
larger-than-expected intersection with some member of a small list - and its
formalization in the low-degree sum-of-squares proof system.
