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]