Name
Abstract | ||
|---|---|---|
We exploit the fact that the set of all polynomials P&egr;@@@@[x1,..,xn] 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;@@@@[x1,..,xn] with deg(P) &equil; d and small integer coefficients such that P@@@@ W(d,n,v). For vn log d lower bounds of this type are beyond our present methods in algebraic complexity theory. |
Year | DOI | Venue |
|---|---|---|
1980 | 10.1145/800141.804674 | STOC |
Keywords | Field | DocType |
testing polynomial,algebraic complexity theory,extended abstract,correct test sequence,known method,zero test,deg w,dim w,lower bound,short correct test sequence,polynomials p,zariski-closed affine,embedding,np hard,approximation algorithm,planar graph | Polynomial identity testing,Discrete mathematics,Combinatorics,Affine space,Polynomial,Test sequence,Planar grid,Multivariate polynomials,Mathematics,Planar graph | Conference |
ISBN | Citations | PageRank |
0-89791-017-6 | 53 | 1.67 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Heintz | 1 | 162 | 19.20 |
| C. P. Schnorr | 2 | 379 | 95.27 |