A zero-test and an interpolation algorithm for the shifted sparse polynomials

Recall that a polynomial $f \in F[X_1, \ldots, X_n]$ is $t$ -sparse, if $f = \sum \alpha_I X^I$ contains at most $t$ terms. In \cite{BT88}, \cite{GKS90} (see also \cite{GK87} and \cite{Ka89}) the problem of interpolation of $t$-sparse polynomial given by a black-box for its evaluation has been solved. In this paper we shall assume that $F$ is a field of characteristic zero. One can consider a $t$-sparse polynomial as a polynomial represented by a straight-line program or an arithmetic circuit of the depth 2 where on the first level there are multiplications with unbounded fan-in and on the second level there is an addition with fan-in $t$. In the present paper we consider a generalization of the notion of sparsity, namely we say that a polynomial $g(X_1, \ldots, X_n) \in F[X_1, \ldots, X_n]$ is {\em shifted $t$-sparse} if for a suitable nonsingular $n \times n$ matrix $A$ and a vector $B$ the polynomial $g(A(X_1, \ldots, X_n)^T+B)$ is $t$-sparse. One could consider $g$ as being represented by a straight-line program of the depth 3 where on the first level (with the fan-in $n+1$) a linear transformation $A(X_1, \ldots, X_n)^T+B$ is computed. One could also consider a shifted $t$-sparse polynomial as $t$-sparse with respect to other coordinates $(Y_1, \ldots, Y_n)^T=A(X_1, \ldots, X_n)^T+B$.