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).