Unconditional Pseudorandom Generators for Low-Degree Polynomials
Theory of Computing, Volume 5(3), pp. 69-82, 2009
Bibliography with links to cited articles
[1] N. Alon, O. Goldreich, J. Håstad, and R. Peralta: Simple construction of almost k-wise independent random variables. Random Structures Algorithms, 3(3):289–304, 1992. [doi:10.1002/rsa.3240030308].
[2] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron: Testing low-degree polynomials over GF(2). In RANDOM-APPROX 2003, volume 2764 of Lecture Notes in Computer Science, pp. 188–199. Springer, 2003. [doi:10.1007/b11961].
[3] M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. [doi:10.1109/18.556674].
[4] E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th STOC, pp. 612–621. ACM Press, 2003. [doi:10.1145/780542.780631].
[5] V. Bergelson, T. Tao, and T. Ziegler: An inverse theorem for the uniformity seminorms associated with the action of Fp∞, 2009. [arXiv:0901.2602].
[6] A. Bogdanov: Pseudorandom generators for low degree polynomials. In Proc. 37th STOC, pp. 21–30. ACM Press, 2005. [doi:10.1145/1060590.1060594].
[7] A. Bogdanov and E. Viola: Pseudorandom bits for polynomials. In Proc. 48th FOCS, pp. 41–51. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.42].
[8] W. T. Gowers: A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11(3):465–588, 2001. [doi:10.1007/s00039-001-0332-9].
[9] B. Green and T. Tao: The distribution of polynomials over finite fields, with applications to the Gowers norms, 2007. [arXiv:0711.3191].
[10] B. Green and T. Tao: An inverse theorem for the Gowers U3(G) norm. Proc. Edinburgh Math. Soc. (Ser. 2), 51(1):73–153, 2008. [doi:10.1017/S0013091505000325].
[11] S. Lovett: Unconditional pseudorandom generators for low degree polynomials. In Proc. 40th STOC, pp. 557–562. ACM Press, 2008. [doi:10.1145/1374376.1374455].
[12] S. Lovett, R. Meshulam, and A. Samorodnitsky: Inverse conjecture for the Gowers norm is false. In Proc. 40th STOC, pp. 547–556. ACM Press, 2008. [doi:10.1145/1374376.1374454].
[13] M. Luby, B. Velickovic, and A. Wigderson: Deterministic approximate counting of depth-2 circuits. In Proc. of the 2nd Israeli Symposium on Theoretical Computer Science (ISTCS’93), pp. 18–24. IEEE Comp. Soc. Press, 1993.
[14] J. Naor and M. Naor: Small-bias probability spaces: Efficient constructions and applications. In Proc. 22nd STOC, pp. 213–223. ACM Press, 1990. [doi:10.1145/100216.100244].
[15] A. Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506–515. ACM Press, 2007. [doi:10.1145/1250790.1250864].
[16] D. Štefankovič: Fourier transforms in computer science. Master’s thesis, University of Chicago, Department of Computer Science, 2000. http://www.cs.rochester.edu/~stefanko/Publications/Fourier.ps.
[17] T. Tao and T. Ziegler: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle, 2008. [arXiv:0810.5527].
[18] E. Viola: The sum of d small-bias generators fools polynomials of degree d. In Proc. 23rd IEEE Conf. on Computational Complexity (CCC), pp. 124–127. IEEE Comp. Soc. Press, 2008. [doi:10.1109/CCC.2008.16].