We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good
coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and
$n$ is the number of vertices):

\begin{itemize}
\item {\em NP-hardness} of finding an independent set of size larger than
$O\left(n \left( \frac{\log \Delta}{\Delta}
\right)^{\frac{1}{r-1}}\right)$ in a $2$-colorable $r-uniform hypergraph for $r \ge 4$. A simple algorithm is known to find
independent sets of size
$\Omega\left(\frac{n}{\Delta^{1/(r-1)}}\right)$ in {\em any} $r$-uniform hypergraph of maximum degree $\Delta$. Under a
combinatorial conjecture on hypergraphs, the $(\log \Delta)^{1/(r-1)}$ factor in our result is necessary.

\item Conditional hardness of finding an independent set with more than
$O\left(\frac{n}{\Delta^{1-c/(k-1)}}\right)$ vertices in a $k$-colorable graph for some absolute constant $c \le 4$, under Khot's
$2$-to-$1$~Conjecture. This suggests the near-optimality of Karger, Motwani and Sudan's
graph coloring algorithm which finds an independent set of size $\Omega\left(\frac{n}{\Delta^{1-2/k}\sqrt{\log \Delta}}\right)$ in
$k$-colorable graphs.

\item Conditional hardness of finding independent sets of size $n \Delta^{-1/8+o_\Delta(1)}$ in almost $2$-colorable
$3$-uniform hypergraphs, under the Unique~Games~Conjecture. This suggests the optimality of the known algorithms to find an independent set of size $\tilde{\Omega}(n \Delta^{-1/8})$ in $2$-colorable $3$-uniform hypergraphs.

\item Conditional hardness of finding an independent set of size more than
$O\left(n \left( \frac{\log \Delta}{\Delta}
\right)^{\frac{1}{r-1}}\right)$
in $r$-uniform hypergraphs that contain an independent set of size
$n \Bigl(1-O\bigl(\frac{\log r}{r}\bigr)\Bigr)$ assuming the Unique
Games Conjecture.

\end{itemize}