Summary: We derandomize results of J. Håstad [Acta Math. 182, No. 1, 105–142 (1999; Zbl 0989.68060)] and U. Feige and J. Kilian [J. Comput. Syst. Sci. 57, No. 2, 187–199 (1998; Zbl 0921.68089)] and show that for all \(\epsilon > 0\), approximating Max Clique and Chromatic Number to within \(n^{1-\epsilon }\) are 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 NqP = qP (where qP stands for quasipolynomial time). 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 J. Bourgain, N. Katz and T. Tao [Geom. Funct. Anal. 14, No. 1, 27–57 (2004; Zbl 1145.11306)]; B. Barak, R. Impagliazzo and A. Wigderson (FOCS ’04); B. Barak et al. [in: Proceedings of the 37th annual ACM symposium on theory of computing 2005 (STOC ’05), 1–10 (2005; Zbl 1192.68468)]; and R. Raz [in: Proceedings of the 37th annual ACM symposium on theory of computing 2005 (STOC ’05), 11–20 (2005; Zbl 1192.68373)].
We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by J. Bourgain [Int. J. Number Theory 1, No. 1, 1–32 (2005; Zbl 1173.11310)].