Fourier growth of degree $2$ polynomials

Abstract

We prove bounds for the absolute sum of all level-$k$ Fourier coefficients for $(-1{)}^{p(x)}$, where polynomial $p:{\mathbf{F}}_2^n\to {\mathbf{F}}_2$ is of degree $1$ or degree $2$.

arXiv comment15 pages