Tight bounds on the Fourier growth of bounded functions on the hypercube

Siddharth Iyer, Anup Rao, Victor Reis +2

We give tight bounds on the degree $\ell$ homogenous parts $f_{\ell }$ of a bounded function $f$ on the cube. We show that if $f:\{\pm 1{\}}^n\to [-1,1]$ has degree $d$, then…