testing polynomials which are easy to compute (extended abstract)
We exploit the fact that the set of all polynomials P&egr;@@@@[x 1 ,..,x n ] of degree ?d which can be evaluated with ?v nonscalar steps can be embedded into a Zariski-closed affine set W(d,n,v),dim W(d,n,v)?(v+1 +n) 2 and deg W(d,n,v)?(2vd) (v+1+n) 2 . As a consequence we prove that for u:&equil; 2v(d+1) 2 and s:&equil; 6(v+1+n) 2 there exist &abarbelow; 1 ,..,&abarbelow; s &egr; [u] n &equil; {1,2,..,u} n such that for all polynomials P&egr;W(d,n,v):P(&abarbelow; 1 ) &equil; p(&abarbelow; 2 ) &equil;...&equil; p(&abarbelow; s ) &equil; O implies P&Xgr;O. This means that &abarbelow; 1 ,...,&abarbelow; s is a correct test sequence for a zero test on all polynomials in W(d,n,v). Moreover, almost every sequence &abarbelow; 1 ,..,&abarbelow; s &egr;[u] n is such a correct test sequence for W(d,n,v). The existence of correct test sequences &abarbelow; 1 ,..,&abarbelow; s &egr; [u] n is established by a counting argument without constructing a correct test sequence. We even show that it is beyond the known methods to establish (i.e. to construct and to prove correctness) of such a short correct test sequence for W(d,n,v). We prove that given such a short, correct test sequence for W(d,n,v) we can efficiently construct a multivariate polynomial P&egr;@@@@[x 1 ,..,x n ] with deg(P) &equil; d and small integer coefficients such that P@@@@ W(d,n,v). For v>n log d lower bounds of this type are beyond our present methods in algebraic complexity theory.
test polynomial computation abstraction exploit embedding correctness sequence argument method log lower bound complexity theory