Optimal testing of Reed-Muller codes

We consider the problem of testing if a given function f:Fn 2F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. proposed and analyzed a natural 2d+1-query test for this property and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are (1)-far with probability (1(d2d)) . We give an asymptotically optimal analysis of their test showing that it rejects functions that are (even only) (2−d)-far with (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 linearity test, for the setting of functions mapping Fn 2 to F 2. The optimality follows from a tighter analysis of counterexamples to the “inverse conjecture for the Gowers norm” constructed by . Our result gives a new relationship between the (d+1)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 -test also improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson. 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 for graph properties.