Linear degree extractors and the inapproximability of max clique and chromatic number

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-α fraction of the randomness, for any α>0.We use our dispersers to derandomize results of Hastad 23 and Feige-Kilian 19 and show that for all ε>0, approximating MAX CLIQUE and CHROMATIC NUMBER to within n1-ε are NP-hard. We also derandomize the results of Khot 29 and show that for some γ > 0, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within n/2(log n)1-γ, unless NP = P.Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao 11, Barak-Impagliazzo-Wigderson 5, Barak-Kindler-Shaltiel-Sudakov-Wigderson 6, and Raz 36. We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain 10.