Linear-Degree Extractors and the NP-Completeness of Approximating Clique and Chromatic Number

SPECIAL COMPUTER SCIENCE/DISCRETE MATH SEMINAR, III
Topic:Linear-Degree Extractors and the NP-Completeness of Approximating Clique and Chromatic Number
Speaker:David Zuckerman
Affiliation:University of Texas
Date:Wednesday, April 13
Time/Room:11:15am - 12:15pm/S-101

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. Extractors have proved useful in a variety of seemingly unrelated areas. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. A similar construction allows us to derandomize the results of Hastad and Feige-Kilian and show that approximating Clique and Chromatic Number to within n^{1-epsilon} are NP-complete, for any epsilon>0. 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 lemmas in the second and third of these papers.