Extractors for polynomial sources over fields of constant order and small characteristic. (English) Zbl 1357.68148
Summary: A polynomial source of randomness over \(\mathbb F_q^n\) is a random variable \(X=f(Z)\) where \(f\) is a polynomial map and \(Z\) is a random variable distributed uniformly over \(\mathbb F_q^r\) for some integer \(r\). The three main parameters of interest associated with a polynomial source are the order \(q\) of the field, the (total) degree \(D\) of the map \(f\), and the base-\(q\) logarithm of the size of the range of \(f\) over inputs in \(\mathbb F_q^r\), denoted by \(k\). For simplicity we call \(X\) a \((q,D,k)\)-source. {
}
Informally, an extractor for \((q,D,k)\)-sources is a function \(E:\mathbb F_q^n\to \{0,1\}^m\) such that the distribution of the random variable \(E(X)\) is close to uniform over \(\{0,1\}^m\) for any \((q,D,k)\)-source \(X\). Generally speaking, the problem of constructing extractors for such sources becomes harder as \(q\) and \(k\) decrease and as \(D\) increases. A rather large number of recent works in the area of derandomization have dealt with the problem of constructing extractors for \((q,1,k)\)-sources, also known as “affine” sources. Constructing an extractor for non-affine sources, i.e., for \(D>1\), is a much harder problem. Prior to the present work, only one construction was known, and that construction works only for fields of order much larger than \(n\) [Z. Dvir et al., Comput. Complexity 18, No. 1, 1–58 (2009; Zbl 1210.68136) (Extended abstract appeared in FOCS 2007)]. In particular, even for \(D=2\), no construction was known for any fixed finite field. In this work we construct extractors for \((q,D,k)\)-sources for fields of constant order. Our proof builds on the work of M. DeVos and A. Gabizon, “Simple affine extractors using dimension expansion.” In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, p. 63 (2010)] on extractors for affine sources. Like the DeVos–Gabizon paper, our result makes crucial use of a theorem of Hou, Leung and Xiang [X.-D. Hou et al., J. Number Theory 97, No. 1, 1–9 (2002; Zbl 1034.11020)] which gives a lower bound on the dimension of products of subspaces.
The preliminary version has appeared in Lect. Notes Comput. Sci. 7408, 399–410 (2012; Zbl 1357.68147).
The preliminary version has appeared in Lect. Notes Comput. Sci. 7408, 399–410 (2012; Zbl 1357.68147).
MSC:
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
| 11T23 | Exponential sums |
| 12E20 | Finite fields (field-theoretic aspects) |
| 60E15 | Inequalities; stochastic orderings |
Keywords:
explicit construction; extractors; field extension; polynomials; polynomials-multivariate; Frobenius automorphisms; character sumsReferences:
| [1] | [1] ELIBEN-SASSON ANDARIELGABIZON: Extractors for polynomials sources over constant-size fields of small characteristic. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), pp. 399–410. Springer, 2012. [doi:10.1007/978-3-642-32512-0_34]665 · Zbl 1357.68147 |
| [2] | [2] ELIBEN-SASSON, SHLOMOHOORY, EYALROZENMAN, SALILVADHAN,ANDAVIWIGDERSON: Extractors for affine sources. Unpublished Manuscript, 2001.668 THEORY OFCOMPUTING, Volume 9 (21), 2013, pp. 665–683680 EXTRACTORS FORPOLYNOMIALSOURCES OVERFIELDS OFCONSTANTORDER |
| [3] | [3] ELIBEN-SASSON ANDSWASTIKKOPPARTY: Affine dispersers from subspace polynomials. SIAM J. Comput., 41(4):880–914, 2012. Preliminary version inSTOC’09. [doi:10.1137/110826254]668 |
| [4] | [4] NORBERTBLUM: A Boolean function requiring 3n network size. Theoret. Comput. Sci., 28(3):337– 345, 1983. [doi:10.1016/0304-3975(83)90029-4]668 |
| [5] | [5] JEANBOURGAIN: On the construction of affine extractors. Geometric and Functional Analysis, 17(1):33–57, 2007. [doi:10.1007/s00039-007-0593-z]668 |
| [6] | [6] LEONARDCARLITZ ANDSABURÔUCHIYAMA: Bounds for exponential sums. Duke Math. J., 24(1):37–41, 1957. [doi:10.1215/S0012-7094-57-02406-7]673 |
| [7] | [7] BENNYCHOR ANDODEDGOLDREICH: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary version inFOCS’85. [doi:10.1137/0217015]667 |
| [8] | [8] ANINDYADE ANDTHOMASWATSON: Extractors and lower bounds for locally samplable sources. ACM Trans. Computation Theory, 4(1):3, 2012. Preliminary version inRANDOM’11. [doi:10.1145/2141938.2141941]668 |
| [9] | [9] EVGENYDEMENKOV ANDALEXANDERS. KULIKOV: An elementary proof of a 3n - o(n) lower bound on the circuit complexity of affine dispersers. In 36th Internat. Symp. on Mathematical Foundations of Computer Science (MFCS’11), pp. 256–265, 2011. [doi:10.1007/978-3-642-229930_25]668 |
| [10] | [10] MATTDEVOS ANDARIELGABIZON: Simple affine extractors using dimension expansion. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 50–57. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.14]666,668,671,674,676,678 |
| [11] | [11] ZEEVDVIR: Extractors for varieties. Comput. Complexity, 21(4):515–572, 2012. Preliminary version inCCC’09. [doi:10.1007/s00037-011-0023-3]668 |
| [12] | [12] ZEEVDVIR, ARIELGABIZON,ANDAVIWIGDERSON: Extractors and rank extractors for polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version inFOCS’07. [doi:10.1007/s00037-009-0258-4]668 |
| [13] | [13] ZEEVDVIR ANDSHACHARLOVETT: Subspace evasive sets. In Proc. 44th STOC, pp. 351–358. ACM Press, 2012. See also atECCC. [doi:10.1145/2213977.2214010]668 · Zbl 1286.94109 |
| [14] | [14] ARIELGABIZON ANDRANRAZ: Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008. Preliminary version inFOCS’05. [doi:10.1007/s00493-0082259-3]668,672,673,678 |
| [15] | [15] VENKATESANGURUSWAMI: Linear-algebraic list decoding of folded Reed-Solomon codes. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 77–85. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.22]668 THEORY OFCOMPUTING, Volume 9 (21), 2013, pp. 665–683681 ELIBEN-SASSON ANDARIELGABIZON |
| [16] | [16] XIANG-DONGHOU, KAHINLEUNG,ANDQINGXIANG: A generalization of an addition theorem of Kneser. J. Number Theory, 97(1):1–9, 2002. [doi:10.1006/jnth.2002.2793]671,672,674 |
| [17] | [17] XINLI: A new approach to affine extractors and dispersers.In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 137–147. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.27]668 |
| [18] | [18] RUDOLFLIDL ANDHARALDNIEDERREITER: Introduction to Finite Fields and Their Applications. Cambridge Univ. Press, Cambridge, 1994.672 |
| [19] | [19] JITSURONAGURA: On the interval containing at least one prime number. Proc. Japan Acad., 28(4):177–181, 1952. [doi:10.3792/pja/1195570997]680 |
| [20] | [20] ANUPRAO: An exposition of Bourgain’s 2-source extractor. Electron. Colloq. on Comput. Complexity (ECCC), 14(034), 2007.ECCC.673 |
| [21] | [21] WOLFGANGM. SCHMIDT: Equations over Finite Fields: An Elementary Approach. Volume 536 of Lecture Notes in Mathematics. Springer, 1976. [doi:10.1007/BFb0080437]673 |
| [22] | [22] RONENSHALTIEL: Dispersers for affine sources with sub-polynomial entropy. In Proc. 52nd FOCS, pp. 247–256. IEEE Comp. Soc. Press, 2011. Full version available atauthor’s home page. [doi:10.1109/FOCS.2011.37]668 |
| [23] | [23] EMANUELEVIOLA: Extractors for circuit sources. In Proc. 52nd FOCS, pp. 220–229. IEEE Comp. Soc. Press, 2011. See also atECCC. [doi:10.1109/FOCS.2011.20]668 · Zbl 1292.68117 |
| [24] | [24] JOHN VONNEUMANN: Various techniques used in connection with random digits. Applied Math Series, 12:36–38, 1951.666 |
| [25] | [25] ANDRÉWEIL: On some exponential sums. Proc. Nat. Acad. Sci. USA, 34(5):204–207, 1948.PNAS. 672 · Zbl 0032.26102 |
| [26] | [26] AMIRYEHUDAYOFF: Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011. [doi:10.1007/s00493-011-2604-9]668 |
| [27] | [27] NOGAZEWI ANDELIBEN-SASSON: From affine to two-source extractors via approximate duality. In Proc. 43rd STOC, pp. 177–186. ACM Press, 2011. [doi:10.1145/1993636.1993661]668 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
