Lower Bounds on Testing Functions of Low Fourier Degree

Pooya Hatami

We consider the problem of testing whether a Boolean function has Fourier degree $\le k$ or it is $\epsilon$-far from any Boolean function with Fourier degree $\le k$. We improve the kn…