Zero testing and equation solving for sparse polynomials on rectangular domains

Abstract

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 $\mathbf{c}\in S^N$ with $f(\mathbf{c})\ne 0$, then there is such a $\mathbf{c}$ in every sphere inside $S^N$, where the radius of the sphere 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_1=\cdots =f_r=0$ inside $S^N$.

References in corpus (2)

• Chevalley Warning type results on abelian groups
• CC-circuits and the expressive power of nilpotent algebras