Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
share
A local tester for an error correcting code C⊆Σ^n is a tester that makes Q oracle queries to a given word w∈Σ^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∈ C. By optimal soundness, we mean that if the tester accepts with probability at least 1-ϵ (where ϵ is small), then it must be the case that w is O(ϵ/Q)-close to some codeword c∈ C in Hamming distance. We show that Generalized Reed-Muller codes admit optimal testers with Q = (3q)^⌈d+1/q-1⌉+O(1) queries. Here, for a prime power q = p^k, the Generalized Reed-Muller code, RM[n,q,d], consists of the evaluations of all n-variate degree d polynomials over 𝔽_q. Previously, no tester achieving this query complexity was known, and the best known testers due to Haramaty, Shpilka and Sudan(which is optimal) and due to Ron-Zewi and Sudan(which was not known to be optimal) both required q^⌈d+1/q-q/p⌉ 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 due to Ron-Zewi and Sudan, and we show that their basic tester is in fact optimal. Our methods are more general and also 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).
READ FULL TEXT