ECCC-Report TR05-100https://eccc.weizmann.ac.il/report/2005/100Comments and Revisions published for TR05-100en-usFri, 16 Sep 2005 07:05:58 +0300
Paper TR05-100
| Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number |
David Zuckerman
https://eccc.weizmann.ac.il/report/2005/100A 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.
Fri, 16 Sep 2005 07:05:58 +0300https://eccc.weizmann.ac.il/report/2005/100