We derandomize results of Håstad (1999) and Feige and Kilian (1998) and show that for all $\epsilon>0$, approximating MAX CLIQUE and CHROMATIC NUMBER to within $n^{1-\epsilon}$ are $\rm NP$-hard. We further derandomize results of Khot (FOCS '01) and show that for some $\gamma>0$, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within $n/2^{(\log n)^{1-\gamma}}$, unless $\rm N\tilde{P} = \rm \tilde{P}$.

The key to these results is a new construction of dispersers, which are related to randomness extractors. A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only $\log_2 n + O(1)$ additional random bits for sources with constant entropy rate, and have constant error. Our dispersers use an arbitrarily small constant times $\log n$ additional random bits for sources with constant entropy rate. Our extractors and dispersers output $1-\alpha$ fraction of the randomness, for any $\alpha>0$.

Our constructions rely on recent results in additive number theory and extractors by Bourgain, Katz, and Tao (2004), Barak, Impagliazzo, and Wigderson (FOCS '04), Barak et al. (STOC '05), and Raz (STOC '05). We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain (2005).