Loss-less condensers, unbalanced expanders, and extractors

ABSTRACT

An extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. Trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. Significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of Trevisan's construction. We give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n-bit input source without losing any min-entropy, using O(\log n) additional random bits. Our condensers are built using a simple modification of Trevisan's construction, and yield the best extractor constructions to date. Loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree D and very strong expansion of (1-\epilon)D. We give other applications of our construction, including dispersers with entropy loss O(\log n), depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 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: N. Alon, 1999. Personal communication.
• 4: Sanjeev Arora , F. T. Leighton , Bruce M. Maggs, On-line Algorithms for Path Selectionin a Nonblocking Network, SIAM Journal on Computing, v.25 n.3, p.600-625, June 1996 [doi>10.1137/S0097539791221499]
• 5: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335357]
• 6: Paul Feldman , Joel Friedman , Nicholas Pippengers, Wide-sense nonblocking networks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.158-173, May 1988 [doi>10.1137/0401018]
• 7: O. Gabber and Z. Galil. Explicit construction of linear sized superconcentrators. Journal of Computer and System Sciences, 22:407-420, 1981.
• 8: O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman. Security preserving amplification of hardness. In 31st FOCS, pages 318-326, 1990.
• 9: Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Near-Optimal Conversion of Hardness into Pseudo-Randomness, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.181, October 17-18, 1999
• 10: Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Extractors and pseudo-random generators with optimal seed length, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.1-10, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335306]
• 11: 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]
• 12: G.A. Margulis. Explicit construction of concentrators. Problems of Inform. Transmission, 9:325-332, 1973.
• 13: 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]
• 14: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 15: 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]
• 16: Nicholas Pippenger, Sorting and selecting in rounds, SIAM Journal on Computing, v.16 n.6, p.1032-1038, December 1, 1987 [doi>10.1137/0216066]
• 17: Jaikumar Radhakrishnan , Amnon Ta-Shma, Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators, SIAM Journal on Discrete Mathematics, v.13 n.1, p.2-24, Jan. 2000 [doi>10.1137/S0895480197329508]
• 18: Ran Raz , Omer Reingold, On recycling the randomness of states in space bounded computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.159-168, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301294]
• 19: Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301292]
• 20: 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
• 21: Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit OR-dispersers with polylogarithmic degree, Journal of the ACM (JACM), v.45 n.1, p.123-154, Jan. 1998 [doi>10.1145/273865.273915]
• 22: Miklos Santha, On using deterministic functions to reduce randomness in probabilistic algorithms, Information and Computation, v.74 n.3, p.241-249, Sept. 1987 [doi>10.1016/0890-5401(87)90023-X]
• 23: Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
• 24: M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996.
• 25: Aravind Srinivasan , David Zuckerman, Computing with Very Weak Random Sources, SIAM Journal on Computing, v.28 n.4, p.1433-1459, Aug. 1999 [doi>10.1137/S009753979630091X]
• 26: Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237877]
• 27: Amnon Ta-Shma, Almost optimal dispersers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.196-202, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276736]
• 28: Luca Trevisan, Construction of extractors using pseudo-random generators (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.141-148, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301289]
• 29: Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999
• 30: L.G. Valiant. Graph theoretic properties in computational complexity. Journal of Computer and System Sciences, 13:278-285, 1976.
• 31: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125-138, 1999.
• 32: D. Zuckerman. General weak random sources. In 31st FOCS, pages 534-543, 1990.
• 33: D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367-391, 1996.
• 34: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Measurement, Performance, Theory, Verification