Fourier bounds and pseudorandom generators for product tests

Chin Ho Lee

We study the Fourier spectrum of functions $f:\{0,1{\}}^{mk}\to \{-1,0,1\}$ which can be written as a product of $k$ Boolean functions $f_i$ on disjoint $m$-bit inputs. We pro…