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.

[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:

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