Zero testing and equation solving for sparse polynomials on rectangular domains
Sprache des Titels:
Englisch
Original Kurzfassung:
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 c?S^N with f(c)?0, then there is such a 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 f1=?=fr=0 inside S^N.
Forschungs-