Lower Bounds on Testing Functions of Low Fourier Degree

We consider the problem of testing whether a Boolean function has Fourier degree $\le k$ or it is $ϵ$-far from any Boolean function with Fourier degree $\le k$. We improve the known lower bound of $\mathrm{\Omega }(k)$ \cite{BBM11,CGM10}, to $\mathrm{\Omega }(k\mathrm{/}\sqrt{ϵ})$. The lower bound uses the recently discovered connections between property testing and communication complexity by Blais $\mathit{\text{et.}}\mathit{\text{al.}}$ \cite{BBM11}