Lower Bounds on Testing Functions of Low Fourier Degree

Abstract

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 known lower bound of $\Omega (k)$ \cite{BBM11,CGM10}, to $\Omega (k/\sqrt{\epsilon })$. The lower bound uses the recently discovered connections between property testing and communication complexity by Blais \textit{et. al.} \cite{BBM11}

This paper has been withdrawn in order to be replaced with a new joint paper with a coauthor