Volume 3 (2007) Article 6 pp. 103-128
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
Received: November 7, 2006
Revised: July 19, 2007
Published: August 6, 2007
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$.