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 n^1-ε 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].

REFERENCES

• 1: M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160:781--793, 2004.
• 2: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 3: Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
• 4: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 5: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 6: Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060592]
• 7: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 8: Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
• 9: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 10: J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1--32, 2005.
• 11: J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis, 14:27--57, 2004.
• 12: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 13: A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30th FOCS, pages 14--19, 1989.
• 14: H. Cramer. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica, pages 23--46, 1937.
• 15: Z. Dvir and R. Raz. An improved analysis of mergers. Technical Report TR05-025, Electronic Colloquium on Computational Complexity, 2005.
• 16: Lars Engebretsen , Jonas Holmerin, Towards optimal lower bounds for clique and chromatic number, Theoretical Computer Science, v.299 n.1-3, p.537-584, 18 April 2003 [doi>10.1016/S0304-3975(02)00535-2]
• 17: U. Feige. Randomized graph products, chromatic numbers, and the Lovasz θ function. Combinatorica, 17:79--90, 1997.
• 18: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 19: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 20: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 21: O. Goldreich. A sample of samplers -- a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997.
• 22: Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6]
• 23: J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105--142, 1999.
• 24: J. Håstad , S. Khot, Query Efficient PCPs with Perfect Completeness, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.610, October 14-17, 2001
• 25: R. Impagliazzo and D. Zuckerman. How to recycle random bits. In 30th FOCS, pages 248--253, 1989.
• 26: Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995 [doi>10.1145/210118.210136]
• 27: Nabil Kahale, Large Deviation Bounds for Markov Chains, Combinatorics, Probability and Computing, v.6 n.4, p.465-474, December 1997 [doi>10.1017/S0963548397003209]
• 28: R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, New York, 1972.
• 29: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 30: S. Konyagin. A sum-product estimate in fields of prime order. Technical report, Arxiv, 2003. http://arxiv.org/abs/math.NT/0304217.
• 31: L. Lovasz. On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383--390, 1975.
• 32: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 33: Elchanan Mossel , Christopher Umans, On the complexity of approximating the VC dimension, Journal of Computer and System Sciences, v.65 n.4, p.660-671, December 2002 [doi>10.1016/S0022-0000(02)00022-3]
• 34: Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546]
• 35: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 36: Ran Raz, Extractors with weak random seeds, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060593]
• 37: O. Reingold , R. Shaltiel , A. Wigderson, Extracting randomness via repeated condensing, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.22, November 12-14, 2000
• 38: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 39: R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67--95, June 2002.
• 40: Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece [doi>10.1145/380752.380790]
• 41: A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50:3015--3025, 2004.
• 42: Amnon Ta-Shma , David Zuckerman , Shmuel Safra, Extractors from Reed-Muller codes, Journal of Computer and System Sciences, v.72 n.5, p.786-812, August 2006 [doi>10.1016/j.jcss.2005.05.010]
• 43: Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999
• 44: Avi Wigderson , David Xiao, A Randomness-Efficient Sampler for Matrix-valued Functions and Applications, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.397-406, October 23-25, 2005 [doi>10.1109/SFCS.2005.8]
• 45: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125--138, 1999.
• 46: D. Zuckerman. General weak random sources. In 31st FOCS, pages 534--543, 1990.
• 47: D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367--391, 1996.
• 48: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Theory

Keywords:
NP-hard, approximation, chromatic number, clique, disperser, explicit construction, extractor, pseudorandom