Abstract:
We consider the problem of testing if a given function $f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. Alon et al.~\cite{AKKLR} proposed and analyzed a natural $2^{d+1}$-query test for this property and showed that it accepts every degree $d$ polynomial with probability $1$, while rejecting functions that are $\Omega(1)$-far with probability $\Omega(1/(d 2^{d}))$. We give an asymptotically optimal analysis of their test showing that it rejects functions that are (even only) $\Omega(2^{-d})$-far with $\Omega(1)$-probability (so the rejection probability is a universal constant independent of $d$ and $n$). Our proof works by induction on $n$, and yields a new analysis of even the classical Blum-Luby-Rubinfeld~\cite{BLR} linearity test, for the setting of functions mapping $\F_2^n$ to $\F_2$. The optimality follows from a tighter analysis of counterexamples to the ``inverse conjecture for the Gowers norm'' constructed by \cite{GT,LMS}. Our result gives a new relationship between the $(d+1)^{\rm{st}}$-Gowers norm of a function and its maximal correlation with degree $d$ polynomials. For functions highly correlated with degree $d$ polynomials, this relationship is asymptotically optimal. Our improved analysis of the \cite{AKKLR}-test also improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson~\cite{VW}. Finally, the optimality of our result also implies a ``query-hierarchy'' result for property testing of linear-invariant properties: For every function $q(n)$, it gives a linear-invariant property that is testable with $O(q(n))$-queries, but not with $o(q(n))$-queries, complementing an analogous result of \cite{GKNR08} for graph properties.