Theory of Computing ------------------- Title : Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number Authors : David Zuckerman Volume : 3 Number : 6 Pages : 103-128 URL : https://theoryofcomputing.org/articles/v003a006 Abstract -------- We derandomize results of Haastad (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 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 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).