Inverse Conjecture for the Gowers Norm is False
by Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky
Theory of Computing, Volume 7(9), pp. 131-145, 2011
Bibliography with links to cited articles
[1] Noga Alon and Richard Beigel: Lower bounds for approximations by low degree polynomials over Zm. In Proc. 16th Ann. IEEE Conf. Comput. Complexity (CCC), pp. 184–187, Washington, DC, USA, 2001. IEEE Comp. Soc. Press. [doi:10.1109/CCC.2001.933885]
[2] Vitaly Bergelson, Terence Tao, and Tamar Ziegler: An inverse theorem for the uniformity seminorms associated with the action of Fp∞. Geom. Funct. Anal., 19:1539–1596, 2010. [doi:10.1007/s00039-010-0051-1]
[3] Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. SIAM J. Comput., 39:2464–2486, April 2010. [doi:10.1137/070712109]
[4] Timothy Gowers: A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11(3):465–588, 2001. [doi:10.1007/s00039-001-0332-9]
[5] Ben Green and Terence Tao: An inverse theorem for the Gowers U3(G) norm. Proc. Edinb. Math. Soc. (2), 51:73–153, 2008. [doi:10.1017/S0013091505000325]
[6] Ben Green and Terence Tao: The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math., 4(2):1–36, 2009. http://cdm.ucalgary.ca/index.php/cdm/article/view/133/98.
[7] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky: Inverse conjecture for the Gowers norm is false. In Proc. 40th STOC, pp. 547–556, New York, NY, USA, 2008. ACM Press. [doi:10.1145/1374376.1374454]
[8] F. J. MacWilliams and N. J. A. Sloane: The Theory of Error Correcting Codes. Amsterdam, North-Holland, 1977.
[9] Alex Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506–515, New York, NY, USA, 2007. ACM Press. [doi:10.1145/1250790.1250864]
[10] Jacob T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. [doi:10.1145/322217.322225]
[11] Terence Tao: Structure and randomness in combinatorics. In Proc. 48th FOCS, pp. 3–15. IEEE Comp. Soc. Press, October 2007. [doi:10.1109/FOCS.2007.17]
[12] Terence Tao: Some notes on “non-classical” polynomials in finite characteristic, 2008. Online blog: http://terrytao.wordpress.com/2008/11/13/some-notes-on-non-classical-polynomials-in-finite-characteristic.
[13] Terence Tao and Tamar Ziegler: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Analysis & PDE, 3(1):1–20, 2010. [doi:10.2140/apde.2010.3.1]
[14] Terence Tao and Tamar Ziegler: The inverse conjecture for the Gowers norm over finite fields in low characteristic. Submitted, 2011.
[15] Emanuele Viola: Guest column: Correlation bounds for polynomials over {0,1}. SIGACT News, 40:27–44, February 2009. [doi:10.1145/1515698.1515709]
[16] Emanuele Viola and Avi Wigderson: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4:137–168, 2008. [doi:10.4086/toc.2008v004a007]