A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes

Over a finite field \({\mathbb{F}}_q\) the (n,d,q)-Reed-Muller code is the code given by evaluations of n-variate polynomials of total degree at most d on all points (of \({\mathbb{F}}_q^n\)). The task of testing if a function \(f:{\mathbb{F}}_q^n \to {\mathbb{F}}_q\) is close to a codeword of an (n,d,q)-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are δ-far from the code with probability Ω(δ). (In this work we allow the constant in the Ω to depend on d.)