Extractor codes

ABSTRACT

We define new error correcting codes based on extractors. We show that for certain choices of parameters these codes have better list decoding properties than are known for other codes, and are provably better than Reed-Solomon codes. We further show that codes with strong list decoding properties are equivalent to slice extractors, a variant of extractors. We give an application of extractor codes to extracting many hardcore bits from a one-way function, using few auxiliary random bits. Finally, we show that explicit slice extractors for certain other parameters would yield optimal bipartite Ramsey graphs.

REFERENCES

• 1: Dan Boneh, Finding smooth integers in short intervals using CRT decoding, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.265-272, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335337]
• 2: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-509, 1952.
• 3: P. Elias. List decoding for noisy channels. In 1957-IRE WESCON Convention Record, Pt. 2, pages 94-104, 1957.
• 4: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 5: V. Guruswami, J. Hastad, M. Sudan, and D. Zuckerman. Combinatorial bounds for list decoding. In Proceedings of the 38th Annual Allerton Conference on Communication, Control, and Computing, pages 603-612, 2000.
• 6: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757-1767, 1999.
• 7: W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13-30, 1963.
• 8: R. Impagliazzo, July 1997. Personal communication. For a written version, see {15}.
• 9: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 10: 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]
• 11: 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]
• 12: 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]
• 13: M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996.
• 14: 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]
• 15: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 16: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]
• 17: 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]
• 18: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125-138, 1999.
• 19: J.M. Wozencraft. List decoding. In Quarterly Progress Report, volume 48, pages 90-95. Research Laboratory of Electronics, MIT, 1958.
• 20: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Design, Performance, Reliability, Theory, Verification