Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic

by Eli Ben-Sasson and Ariel Gabizon

Theory of Computing, Volume 9(21), pp. 665-683, 2013

Bibliography with links to cited articles

[1]   Eli Ben-Sasson and Ariel Gabizon: 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]

[2]   Eli Ben-Sasson, Shlomo Hoory, Eyal Rozenman, Salil Vadhan, and Avi Wigderson: Extractors for affine sources. Unpublished Manuscript, 2001.

[3]   Eli Ben-Sasson and Swastik Kopparty: Affine dispersers from subspace polynomials. SIAM J. Comput., 41(4):880–914, 2012. Preliminary version in STOC’09. [doi:10.1137/110826254]

[4]   Norbert Blum: A Boolean function requiring 3n network size. Theoret. Comput. Sci., 28(3):337–345, 1983. [doi:10.1016/0304-3975(83)90029-4]

[5]   Jean Bourgain: On the construction of affine extractors. Geometric and Functional Analysis, 17(1):33–57, 2007. [doi:10.1007/s00039-007-0593-z]

[6]   Leonard Carlitz and Saburô Uchiyama: Bounds for exponential sums. Duke Math. J., 24(1):37–41, 1957. [doi:10.1215/S0012-7094-57-02406-7]

[7]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary version in FOCS’85. [doi:10.1137/0217015]

[8]   Anindya De and Thomas Watson: Extractors and lower bounds for locally samplable sources. ACM Trans. Computation Theory, 4(1):3, 2012. Preliminary version in RANDOM’11. [doi:10.1145/2141938.2141941]

[9]   Evgeny Demenkov and Alexander S. 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-22993-0_25]

[10]   Matt DeVos and Ariel Gabizon: 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]

[11]   Zeev Dvir: Extractors for varieties. Comput. Complexity, 21(4):515–572, 2012. Preliminary version in CCC’09. [doi:10.1007/s00037-011-0023-3]

[12]   Zeev Dvir, Ariel Gabizon, and Avi Wigderson: Extractors and rank extractors for polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version in FOCS’07. [doi:10.1007/s00037-009-0258-4]

[13]   Zeev Dvir and Shachar Lovett: Subspace evasive sets. In Proc. 44th STOC, pp. 351–358. ACM Press, 2012. See also at ECCC. [doi:10.1145/2213977.2214010]

[14]   Ariel Gabizon and Ran Raz: Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415–440, 2008. Preliminary version in FOCS’05. [doi:10.1007/s00493-008-2259-3]

[15]   Venkatesan Guruswami: 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]

[16]   Xiang-Dong Hou, Ka Hin Leung, and Qing Xiang: A generalization of an addition theorem of Kneser. J. Number Theory, 97(1):1–9, 2002. [doi:10.1006/jnth.2002.2793]

[17]   Xin Li: 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]

[18]   Rudolf Lidl and Harald Niederreiter: Introduction to Finite Fields and Their Applications. Cambridge Univ. Press, Cambridge, 1994.

[19]   Jitsuro Nagura: On the interval containing at least one prime number. Proc. Japan Acad., 28(4):177–181, 1952. [doi:10.3792/pja/1195570997]

[20]   Anup Rao: An exposition of Bourgain’s 2-source extractor. Electron. Colloq. on Comput. Complexity (ECCC), 14(034), 2007. ECCC.

[21]   Wolfgang M. Schmidt: Equations over Finite Fields: An Elementary Approach. Volume 536 of Lecture Notes in Mathematics. Springer, 1976. [doi:10.1007/BFb0080437]

[22]   Ronen Shaltiel: Dispersers for affine sources with sub-polynomial entropy. In Proc. 52nd FOCS, pp. 247–256. IEEE Comp. Soc. Press, 2011. Full version available at author’s home page. [doi:10.1109/FOCS.2011.37]

[23]   Emanuele Viola: Extractors for circuit sources. In Proc. 52nd FOCS, pp. 220–229. IEEE Comp. Soc. Press, 2011. See also at ECCC. [doi:10.1109/FOCS.2011.20]

[24]   John von Neumann: Various techniques used in connection with random digits. Applied Math Series, 12:36–38, 1951.

[25]   André Weil: On some exponential sums. Proc. Nat. Acad. Sci. USA, 34(5):204–207, 1948. PNAS.

[26]   Amir Yehudayoff: Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011. [doi:10.1007/s00493-011-2604-9]

[27]   Noga Zewi and Eli Ben-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]