Affine dispersers from subspace polynomials

ABSTRACT

An affine disperser over F₂ⁿ for sources of dimension d is a function f: F₂ⁿ → F₂ such that for any affine space S ⊆ F₂ⁿ of dimension at least d, we have {f(s) : s in S} = F₂. Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every d = Ω(n), due to Barak et. al.[2] and Bourgain[10] (the latter in fact gives stronger objects called affine extractors). In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d = Ω(n^4/5). The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.

REFERENCES

• 1: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 2: 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]
• 3: Boaz Barak , Anup Rao , Ronen Shaltiel , Avi Wigderson, 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132611]
• 4: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007361]
• 5: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Short PCPs Verifiable in Polylogarithmic Time, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.120-134, June 11-15, 2005 [doi>10.1109/CCC.2005.27]
• 6: E. Ben-Sasson, S. Hoory, E. Rozenman, and S. Vadhan. Extractors for affine sources, unpublished manuscript. 2001.
• 7: Eli Ben-Sasson , Swastik Kopparty , Jaikumar Radhakrishnan, Subspace Polynomials and List Decoding of Reed-Solomon Codes, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.207-216, October 21-24, 2006 [doi>10.1109/FOCS.2006.73]
• 8: Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060631]
• 9: E. R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, revised 1984 edition, 1968.
• 10: J. Bourgain. On the construction of affine extractors. Geometric and Functional Analysis, 17(1):33--57, 2007.
• 11: J. Bourgain, A. A. Glibichuk, and S. V. Konyagin. Estimates for the number of sums and products and for exponential sums in fields of prime order. J. London Math. Soc. (2), 73(2):380--398, 2006.
• 12: J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geom. Funct. Anal., 14(1):27--57, 2004.
• 13: Benny Chor , Oded Goldreich , Johan Hasted , Joel Freidmann , Steven Rudich , Roman Smolensky, The bit extraction problem or t-resilient functions, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.396-407, October 21-23, 1985 [doi>10.1109/SFCS.1985.55]
• 14: Ariel Gabizon , Ran Raz , Ronen Shaltiel, Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed, SIAM Journal on Computing, v.36 n.4, p.1072-1094, December 2006 [doi>10.1137/S0097539705447049]
• 15: Ariel Gabizon , Ran Raz, Deterministic Extractors for Affine Sources over Large Fields, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.407-418, October 23-25, 2005 [doi>10.1109/SFCS.2005.31]
• 16: Jesse Kamp , Anup Rao , Salil Vadhan , David Zuckerman, Deterministic extractors for small-space sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132613]
• 17: Jesse Kamp , David Zuckerman, Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography, SIAM Journal on Computing, v.36 n.5, p.1231-1247, December 2006 [doi>10.1137/S0097539705446846]
• 18: R. Lidl and H. Niederreiter. Finite fields, volume 20 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 1997.
• 19: O. Ore. On a special class of polynomials. Trans. Amer. Math. Soc., 35(3):559--584, 1933.
• 20: O. Ore. Contributions to the theory of finite fields. Trans. Amer. Math. Soc., 36(2):243--274, 1934.
• 21: R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67--95, 2002.
• 22: L. Trevisan , S. Vadhan, Extracting randomness from samplable distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.32, November 12-14, 2000
• 23: 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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Theory

Keywords:
extractors, randomness