Zero testing and equation solving for sparse polynomials on rectangular domains

We consider sparse polynomials in N variables over a finite field, and ask whether they vanish on a set S^N, where S is a set of nonzero elements of the field. We see that if for a polynomial f, there is [Formula presented] with [Formula presented], then there is such a [Formula presented] in every ball (with respect to the Hamming distance) inside S^N, where the radius of the ball is bounded by a multiple of the logarithm of the number of monomials that appear in f. A similar result holds for the solutions of the equations f₁=⋯=f_r=0 inside S^N. When 0∉S, this provides algorithms for testing whether a given polynomial f vanishes on S^N and for checking whether f₁=⋯=f_r=0 has a solution in S^N that are of time complexity in O(n^clog⁡(n)), where c>0 and n is the size of the input polynomials given in sparse representation.