Unconditional Pseudorandom Generators for Low-Degree Polynomials

by Shachar Lovett

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].