Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-100 | 30th August 2005 00:00

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number


Authors: David Zuckerman
Publication: 16th September 2005 07:05
Downloads: 1252


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.

ISSN 1433-8092 | Imprint