Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

A local tester for an error correcting code $C\subseteq\Sigma^{n}$ is a tester that makes Q oracle queries to a given word $w\in\bar{\Sigma}^{n}$ and decides to accept or reject the word w. An optimal local tester is a local tester that has the additional properties of completeness and optimal soundness. By completeness, we mean that the tester must accept with probability 1 if $w\in C$. By optimal soundness, we mean that if the tester accepts with probability at least $1-\varepsilon$ (where $\varepsilon$ is small), then it must be the case that w is $O(\varepsilon/Q)$-close to some codeword $c\in C$ in Hamming distance. We show that Generalized Reed-Muller codes admit optimal testers with $Q=(C_{p}q)^{\lceil\frac{d+1}{q-1}\rceil+O(1)}$ queries for $C_{p}=(2p-1)^{\frac{1}{p-1}}$. Here, for a prime power $q=p^{k}$, the Generalized Reed-Muller code, $\operatorname{RM}[n, q, d]$, consists of the evaluations of all n-variate degree d polynomials over $\mathbb{F}_{q}$. As $p,q$, and d go to infinity, Q matches the known lower bound of $q^{\frac{d+1}{q-1}}$ up to a multiplicative factor of 1. Previously, no tester achieving this query complexity was known, and the best known testers due to Haramaty, Shpilka and Sudan [21] (which is optimal) and due to Ron-Zewi and Sudan [33](which was not known to be optimal) both required $q^{\lceil\frac{d+1}{q-q/p}\rceil}$ queries. Our tester achieves query complexity which is polynomially better than by a power of $p/(p-1)$, which is nearly the best query complexity possible for generalized Reed-Muller codes. The tester we analyze is constructed using the same framework of Ron-Zewi and Sudan, and in fact our analysis shows that their tester is optimal as well. More generally, our methods allow us to prove that a wide class of testers, which follow the form of the Ron-Zewi and Sudan tester, are optimal. This result applies to testers for all affine-invariant codes (which are not necessarily generalized Reed-Muller codes).