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 n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, which 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.

We use our dispersers to derandomize the results of Hastad and Feige-Kilian and show that for all epsilon>0, approximating Clique and
Chromatic Number to within n^{1-epsilon} are NP-complete. We also derandomize the results of Khot and show that for some gamma>0, no quasi-polynomial time algorithm approximates Clique or Chromatic Number to within n/2^{(log n)^{1-gamma}}, unless quasi-NP = quasi-P.

Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao, Barak-Impagliazzo-Wigderson, Barak-Kindler-Shaltiel-Sudakov-Wigderson, and Raz. We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain.