Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes

ABSTRACT

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005].

Our expanders can be interpreted as near-optimal “randomness condensers,” that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)).

REFERENCES

• 1: Roy Armoni, On the Derandomization of Space-Bounded Computations, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.47-59, October 08-10, 1998
• 2: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are Bitvectors Optimal?, SIAM Journal on Computing, v.31 n.6, p.1723-1744, 2002 [doi>10.1137/S0097539702405292]
• 3: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 4: 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]
• 5: A. Cohen , A. Wigderson, Dispersers, deterministic amplification, and weak random sources, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.14-19, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63449]
• 6: Gabber, O., and Galil, Z. 1981. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 3 (June), 407--420.
• 7: David Galvin , Prasad Tetali, Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs, Random Structures & Algorithms, v.28 n.4, p.427-443, July 2006 [doi>10.1002/rsa.v28:4]
• 8: 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]
• 9: Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties: a quality-size trade-off for hashing, Random Structures & Algorithms, v.11 n.4, p.315-343, Dec. 1997
• 10: Guruswami, V., Hastad, J., Sudan, M., and Zuckerman, D. 2002. Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48, 5, 1021--1035.
• 11: Guruswami, V., and Rudra, A. 2008. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory 54, 1 (Jan.), 135--150. (Preliminary version appeared in STOC 2006.)
• 12: Guruswami, V., and Sudan, M. 1999. Improved decoding of Reed-Solomon and Algebraic-Geometry codes. IEEE Trans. Inf. Theory 45, 6, 1757--1767.
• 13: Guruswami, V., Umans, C., and Vadhan, S. 2006. Extractors and condensers from univariate polynomials. Tech. Rep. TR06-134, Electronic Colloquium on Computational Complexity. October.
• 14: Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
• 15: Hoory, S., Linial, N., and Wigderson, A. 2006. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43, 4, 439--561 (electronic).
• 16: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 17: 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]
• 18: R. Impagliazzo , D. Zuckerman, How to recycle random bits, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.248-253, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63486]
• 19: 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]
• 20: Kalyanaraman, S. and Umans, C. 2006. On obtaining pseudo-randomness from error-correcting codes. In FSTTCS, S. Arun-Kumar and N. Garg, Eds. Lecture Notes in Computer Science, vol. 4337. Springer-Verlag, New York, 105--116.
• 21: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 22: Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780630]
• 23: Lubotzky, A., Phillips, R., and Sarnak, P. 1988. Ramanujan graphs. Combinatorica 8, 3, 261--277.
• 24: Margulis, G. A. 1973. Explicit constructions of expanders. Probl. Peredači Inf. 9, 4, 71--80.
• 25: Margulis, G. A. 1988. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Probl. Peredachi Inf. 24, 1, 51--60.
• 26: Nelson, J., and Woodruff, D. P. 2008. Revisiting norm estimation in data streams. CoRR abs/0811.3648.
• 27: 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]
• 28: 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]
• 29: Farzad Parvaresh , Alexander Vardy, Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.285-294, October 23-25, 2005 [doi>10.1109/SFCS.2005.29]
• 30: 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]
• 31: Anup Rao , David Zuckerman, Extractors for Three Uneven-Length Sources, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_44]
• 32: Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Journal of Computer and System Sciences, v.65 n.1, p.97-128, August 2002 [doi>10.1006/jcss.2002.1824]
• 33: Omer Reingold , Ronen Shaltiel , Avi Wigderson, Extracting Randomness via Repeated Condensing, SIAM Journal on Computing, v.35 n.5, p.1185-1209, 2006 [doi>10.1137/S0097539703431032]
• 34: Reingold, O., Vadhan, S. P., and Wigderson, A. 2001. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Electron. Colloq. Comput. Complex. (ECCC) 8, 18.
• 35: Shaltiel, R. 2002. Recent developments in explicit constructions of extractors. Bull. European Assoc. Theoret. Comput. Sci. 77, 67--. Columns: Computational Complexity.
• 36: Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005 [doi>10.1145/1059513.1059516]
• 37: Shoup, V. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comput. 54, 189, 435--447.
• 38: 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]
• 39: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
• 40: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR lemma, Journal of Computer and System Sciences, v.62 n.2, p.236-266, March 2001 [doi>10.1006/jcss.2000.1730]
• 41: Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002 [doi>10.1016/S0020-0190(02)00206-5]
• 42: Amnon Ta-Shma , Christopher Umans, Better lossless condensers through derandomized curve samplers, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.177-186, October 21-24, 2006 [doi>10.1109/FOCS.2006.18]
• 43: Amnon Ta-Shma , Christopher Umans† , David Zuckerman‡, Lossless Condensers, Unbalanced Expanders, And Extractors, Combinatorica, v.27 n.2, p.213-240, March 2007 [doi>10.1007/s00493-007-0053-2]
• 44: Ta-Shma, A., and Zuckerman, D. 2004. Extractor codes. IEEE Trans. Inf. Theory 50, 12, 3015--3025.
• 45: 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]
• 46: Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001 [doi>10.1145/502090.502099]
• 47: Christopher Umans, Pseudo-random generators for all hardnesses, Journal of Computer and System Sciences, v.67 n.2, p.419-440, September 2003 [doi>10.1016/S0022-0000(03)00046-1]
• 48: Wigderson, A., and Zuckerman, D. 1999. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica 19, 1, 125--138.
• 49: Zuckerman, D. 1996. Simulating BPP using a general weak random source. Algorithmica 16, 4-5, 367--391.
• 50: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997
• 51: David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132612]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL

  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:
Expander graphs, condensers, error-correcting codes, list decoding, randomness extractors