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

m a t h b f c i n S^{N}

with

f (m a t h b f c) e q 0

, then there is such a

m a t h b f 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} = c d o t s = f_{r} = 0

inside

S^{N}

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Zero testing and equation solving for sparse polynomials on rectangular domains