Lower Bounds on Testing Functions of Low Fourier Degree
Pooya Hatami · arXiv (Cornell University) · 2012
We consider the problem of testing whether a Boolean function has Fourier degree $\leq k$ or it is $ε$-far from any Boolean function with Fourier degree $\leq k$. We improve the known lower bound of $Ω(k)$ \cite{BBM11,CGM10}, to $Ω(k/\sqrtε)$. The lower bound uses the recently discovered connections between property testing and communication complexity by Blais \textit{et. al.} \cite{BBM11}