Name
Title | ||
|---|---|---|
Linear degree extractors and the inapproximability of max clique and chromatic number |
Abstract | ||
|---|---|---|
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-α fraction of the randomness, for any α>0.We use our dispersers to derandomize results of Hastad [23] and Feige-Kilian [19] and show that for all ε>0, approximating MAX CLIQUE and CHROMATIC NUMBER to within n1-ε are NP-hard. We also derandomize the results of Khot [29] and show that for some γ > 0, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within n/2(log n)1-γ, unless NP = P.Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao [11], Barak-Impagliazzo-Wigderson [5], Barak-Kindler-Shaltiel-Sudakov-Wigderson [6], and Raz [36]. We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain [10]. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1132516.1132612 | Theory of Computing |
Keywords | Field | DocType |
constant entropy rate,CHROMATIC NUMBER,additional random bit,log n,low-quality random source,n additional random bit,random bit,dispersers output,randomness extractor,small constant time,chromatic number,linear degree extractor,max clique | Discrete mathematics,Binary logarithm,Randomness extractor,Entropy rate,Combinatorics,Clique,Chromatic scale,Mathematics,Additive number theory,Randomness,Pseudorandom number generator | Journal |
Volume | Issue | ISBN |
3 | 1 | 1-59593-134-1 |
Citations | PageRank | References |
168 | 6.96 | 39 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Zucherman | 1 | 2588 | 266.65 |