A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynomials

Dima Grigoriev^{⋆}^{1} and Marek Karpinski ^{⋆⋆}^{2}

1 Dept. of Computer Science, the Pennsylvania State University, University Park,

PA 16802

2 Dept. of Computer Science, University of Bonn, 5300 Bonn 1, and International Computer Science Institute, Berkeley, California

Abstract. Recall that a polynomial f ∈ F [X_{1}, …, X_{n}] is t -sparse, if f = ∑ α_{I}X^{I} contains at most t terms. In [BT 88], [GKS 90] (see also [GK 87] and [Ka 89]) 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 tsparse 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}, …, X_{n}) ∈ F [X_{1}, …, X_{n}] is shifted t-sparse if for a suitable nonsingular n × n matrix A and a vector B the polynomial g(A(X_{1}, …, 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}, …, 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}, …, Y_{n})^{T} = A(X_{1}, …, X_{n})^{T} + B. We assume that a shifted t-sparse polynomial g is given by a black-box and the problem we consider is to construct a transformation A(X_{1}, …, X_{n})^{T} + B. As the complexity of the designed below algorithm (see the Theorem in which we describe the variety of all possible A, B and the corresponding t-sparse representations of g(A(X_{1}, …, X_{n})^{T} + B)) depends on d^{n^{4}} where d is the degree of g, we could first interpolate g within time d^{O(n)} and suppose that g is given explicitly. It would be interesting to get rid of d in the complexity bounds as it is usually done in the interpolation of sparse polynomials ([BT 88], [GKS 90], [Ka 89]). The main technical tool we rely on is the criterium of t-sparsity based on Wronskian ([GKS 91], [GKS 92]), the latter criterium has a parametrical nature (so we can select t-sparse polynomials from a given parametrical family of polynomials) unlike the approach in [BT 88] using BCH-codes.

⋆ Work partially done while visiting the Dept. of Computer Science, University of Bonn. On leave from the Steklov Mathematical Institute, Fontanka 27, St. Petersburg, 191011 Russia

⋆⋆ Supported in part by Leibniz Center for Research in Computer Science, by the DFG Grant KA 673/4-1 and by the SERC Grant GR-E 68297 We could directly consider (see the Theorem) the multivariate polynomials (section 3), but to make the exposition clearer before that we first study (see the proposition) the one-variable case (section 2). First at all we recall (section 1) the criterium of t-sparsity and based on it interpolation method for t-sparse multivariable polynomials. In the last section 4 we design a zero-test algorithm for shifted t-sparse polynomials with the complexity independent on d.

1 A Criterium of t-sparsity and the Interpolation

Let p_{1}, …, p_{n} be pairwise distinct primes and denote by D a linear operator mapping D : X_{1} → p_{1}X_{1}, …, D : X_{n} → p_{n}X_{n}. We recall a criterium of tsparsity (cf. also [BT 88]). Lemma 1. ([GKS 91], [GKS 92]) A polynomial f ∈ F [X_{1}, …, X_{n}] is t-sparse if and only if the Wronskian

W_{f}(X_{1}, …, X_{n}) = det ( \begin{matrix}f & Df & … & D^{t}f \\ Df & D^{2}f & … & D^{t+1}f \\ ⋮ & ⋮ & & ⋮ \\ D^{t}f & D^{t+1}f & … & D^{2t}f \end{matrix} ) ∈ F [X_{1}, …, X_{n}]

vanishes identically.

An interpolation method from [BT 88] (see also [KY 88]) actually considers the Wronskian W_{f}(1, …, 1) at the point (1, …, 1) and is based on the following Lemma 2. ([BT 88]) If f is exactly t-sparse (i.e., f contains exactly t terms), then the reduced Wronskian does not vanish

W̄_{f}(1, …, 1) = det ( \begin{matrix}f(1, …, 1) & (Df)(1, …, 1) & … & (D^{t−1}f)(1, …, 1) \\ ⋮ & ⋮ & & ⋮ \\ (D^{t−1}f)(1, …, 1) & (D^{t}f)(1, …, 1) & … & (D^{2t−2}f)(1, …, 1) \end{matrix} ) ≠ 0

at the point (1, …, 1).

Thus, if f = ∑ α_{I}X^{I} is exactly t-sparse and if a (characteristic) polynomial χ(Z) = ∑_{0≤j≤t} γ_{j}Z^{j} ∈ [Z] has as its t roots p^{I} for all exponent vectors I occuring

in f (where for I = (i_{1}, …, i_{n}) we denote p^{I} = p_{1}^{i_{1}} ⋯ p_{n}^{i_{n}}), then ∑_{0≤j≤t} γ_{j}D^{j}f = 0

and hence

( \begin{matrix}f & Df & … & D^{t}f \\ ⋮ & ⋮ & & ⋮ \\ D^{t}f & D^{t+1}f & … & D^{2t}f \end{matrix} ) (γ_{0}, …, γ_{t})^{T} = 0 .

Therefore, a linear system

( \begin{matrix}f(1, …, 1) & (Df)(1, …, 1) & … & (D^{t}f)(1, …, 1) \\ ⋮ & ⋮ & & ⋮ \\ (D^{t}f)(1, …, 1) & (D^{t+1}f)(1, …, 1) & … & (D^{2t}f)(1, …, 1) \end{matrix} ) (Y_{0}, …, Y_{t})^{T} = o

has (up to a constant multiple) a unique (by lemma 2) solution (Y_{0}, …, Y_{t}) = (γ_{0}, …, γ_{t}) which gives the coefficients of χ, thereby its roots p^{I} and finally I.

2 One-variable Shifted Sparse Polynomials

A polynomial g ∈ F [X] is called shifted t-sparse if for an appropriate b a polynomial g(X − b) is t-sparse (so the origin is shifted from 0 to b). If t is the least possible, we say that g is minimally shifted t-sparse, this notion relates also to the multivariable case. Let F = . Usually we take b from the algebraic closure ¯ (we could also consider b from ). Assume that the bit-size of the (rational) coefficients of g does not exceed M.

Consider a new variable Y and an (Y)-linear transformation of the ring (Y)[X] mapping D_{1} : X → p_{1}X + (p_{1} − 1)Y. Denote

W_{g}(X, Y) = det ( \begin{matrix}g & D_{1}g & … & D_{1}^{t}g \\ ⋮ & ⋮ & & ⋮ \\ D_{1}^{t}g & D_{1}^{t+1}g & … & D_{1}^{2t}g \end{matrix} ) ∈ [X, Y]

Lemma 3. g is shifted t-sparse if and only if for some Y = b a polynomial W_{g}(X, b) vanishes identically. Moreover in this case a polynomial g(X − b) is t-sparse. Proof. If g(X − b) is t-sparse, then the expansion g = ∑_{j} β_{j}(X + b)^{j} into the powers of (X +b) contains at most t terms. Lemma 1 implies that W_{g}(X, b) vanishes identically. The other direction follows also from lemma 1 which completes the proof.

Observe that for almost every b the polynomial g(X − b) has exactly (d + 1) terms, where d = deg(g), since in the polynomial g(X − Y) ∈ [X, Y] the coefficient in the power X^{S} is a polynomial in Y of degree exactly d − S, 0 ≤ S ≤ d.

Lemma 3 provides an algorithm for finding t such that g is minimal shifted t-sparse which runs in time d^{O(1)} (trying successively t = 1, 2, …), moreover this algorithm finds all Y = Y_{0} such that g(X − Y_{0}) is t-sparse. Namely, one writes down a polynomial system in Y equating to zero all the coefficients in the powers of X, thus the system contains d^{O(1)} equations of degrees at most d^{O(1)}. So, one can prove the following proposition. Proposition. There is an algorithm which for one-variable polynomial g finds the minimal t and all Y_{0} for which g(X − Y_{0}) is t-sparse in time (Md)^{O(1)}. The number of such Y_{0} does not exceed d^{O(1)}.

One of the purposes of the sparse analysis is to get rid of d in the complexity bounds. We can write down a system in b with a less (for small t) number of equations, when b is supposed to belong to . So, assume that the expansion g = ∑_{j} β_{j}(X + b)^{j} contains at most t terms for some b ∈ . Then for any

fixed Y = Y_{0} ∈ a polynomial (D_{1}^{K}g)(X, Y_{0}) = ∑_{j} β_{j}(p_{1}^{K}(X + Y_{0}) − Y_{0} + b)^{j}

for K ≥ 0. Therefore the polynomial W_{g}(X, Y_{0}) has at most 2^{O(t^{4})} real roots because of [Kh 91] since one can consider (2t + 1)t powers of linear polynomials (p_{1}^{K}(X +Y_{0})−Y_{0} +b)^{j}, 0 ≤ K ≤ 2t as the elements of a Pfaffian chain [Kh 91].

Thus Y satisfies the conditions of lemma 3 if and only if it satisfies the following system of polynomial equations (cf. lemma 5 below)

W_{g}(0, Y) = W_{g}(1, Y) = … = W_{g}(2^{O(t^{4})}, Y) = 0 .

Each of the polynomials from the latter system can be represented by a blackbox for its evaluation. As each of these polynomials W_{g}(s, Y) contains (2t + 1)t powers (p_{1}^{K}(s + Y) − Y + b)^{j}, 0 ≤ K ≤ 2t the system has at most 2^{O(t^{4})} real solutions (by the same argument relying on [Kh 91] as above), thus the number of such Y = Y_{0} that g(X − Y_{0}) is t-sparse is less than 2^{O(t^{4})}.

3 Multivariate Shifted Sparse Polynomials

Consider now n^{2}+n new variables Z_{i,j}, Y_{i}, 1 ≤ i, j ≤ n and a ({Z_{ij}, Y_{i}}_{1≤i,j≤n})- linear transformation D_{n} of the ring ({Z_{ij}, Y_{i}}_{1≤i,j≤n})[X_{1}, …, X_{n}] mapping

D_{n}X = ZP Z^{−1}(X − Y) + Y

where vectors X = (X_{1}, …, X_{n})^{T} , Y = (Y_{1}, …, Y_{n})^{T}, matrices Z = (Z_{ij}), P =

( \begin{matrix}p_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & p_{n} \end{matrix} ). Similarly, as above denote

W_{g}(X, Y, Z) = det ( \begin{matrix}g & D_{n}g & … & D_{n}^{t}g \\ ⋮ & ⋮ & & ⋮ \\ D_{n}^{t}g & D_{n}^{t+1}g & … & D_{n}^{2t}g \end{matrix} ) ∈ (Z)[X, Y] .

Lemma 4. g is shifted t-sparse if and only if for some Z_{0}, Y_{0} such that detZ_{0} ≠ 0, the polynomial W_{g}(X, Y_{0}, Z_{0}) vanishes identically. Moreover, in this case a polynomial g(Z_{0}X + Y_{0}) is t-sparse.

The proof is similar to the proof of lemma 3 taking into account that

(D_{n}g)(ZX + Y) = g(ZP Z^{−1}(ZX + Y − Y) + Y) = g(ZP X + Y) .

As in section 2 lemma 4 provides a test for minimal shifted t-sparsity trying successively t = 1, 2, … running in time d^{O(n^{4})} (see [CG 83] for solving system of polynomial equations and inequalities). Moreover, the algorithm finds algebraic conditions (equations and inequality det Z ≠ 0) on all Z, Y for which g(ZX +Y) is t-sparse.

So, these Z, Y form a constructive set U ⊂ ^{ n̄^{2}+n} given by a system h_{1} = … = h_{k} = 0, det Z ≠ 0 where h_{1}, …, h_{k} ∈ [{Z_{ij}, Y_{i}}_{1≤i,j≤n}], then deg(h_{1}), …, deg(h_{k}) ≤ d^{O(1)}, k ≤ d^{O(1)}. Applying the algorithm from [CG 83] one can find the irreducible over components Ū = ⋃_{l} U^{(l)} of the closure (in the

Zariski topology) Ū. For each component U^{(l)} the algorithm from [CG 83] produces firstly, some polynomials h_{1}^{(l)}, …, h_{N(l)}^{(l)} ∈ [{Z_{ij}, Y_{i}}] such that U^{(l)} = {h_{1}^{(l)} = … = h_{N(l)}^{(l)} = 0} and secondly, a general point of U^{(l)}, namely the following fields isomorphism

(U^{(l)}) ≃ (T_{1}, …, T_{m})[θ]

where (U^{(l)}) is the field of rational functions on U^{(l)}, m = dim(U^{(l)}), linear forms T_{1}, …, T_{m} in variables {Z_{ij}, Y_{i}}_{1≤i,j≤n} constitute a transcendental basis of (U^{(l)}) and θ is algebraic over (T_{1}, …, T_{m}). The algorithm produces a minimal polynomial ϕ(Z) ∈ (T_{1}, …, T_{m})[Z] of θ, the linear forms T_{S}({Z_{ij}, Y_{i}}), 1 ≤ S ≤ m, a linear form θ({Z_{ij}, Y_{i}}), and the expressions for the coordinate functions Z_{i,j}(T_{1}, …, T_{m}, θ), Y_{i}(T_{1}, …, T_{m}, θ) as rational functions in T_{1}, …, T_{m}, θ. The degrees of the polynomials h_{1}^{(l)}, …, h_{N(l)}^{(l)} do not exceed d^{O(n^{2})}, the bit-size of any of the (rational) coefficients occuring in these polynomials can be bounded by M^{O(1)}d^{O(n^{2})} and the algorithm runs in time M^{O(1)}d^{O(n^{4})}.

Denote Ũ^{(l)} = U^{(l)} \ {det Z = 0} (some of Ũ^{(l)} can be empty), remark that

U = ⋃_{l} Ũ^{(l)}.

For any point (Z_{0}, Y_{0}) ∈ Ũ^{(l)} the polynomial g(Z_{0}X +Y_{0}) is exactly t-sparse, therefore by lemma 2 the following linear system

( \begin{matrix}g(X_{0}, Y_{0}, Z_{0}) & D_{n}g(X_{o}, Y_{0}, Z_{0}) & … & D_{n}^{t}g(X_{0}, Y_{0}, Z_{0}) \\ ⋮ & ⋮ & & ⋮ \\ D_{n}^{t}g(X_{0}, Y_{0}, Z_{0}) & D_{n}^{t+1}g(X_{0}, Y_{0}, Z_{0}) & … & D_{n}^{2t}g(X_{0}, Y_{0}, Z_{0}) \end{matrix} ) (γ_{0}, …, γ_{t−1}, 1) = 0

has a unique solution, where the vector X_{0} = Z_{0}^{−1}((1, …, 1)^{T} − Y_{0}). As γ_{0}, …, γ_{t−1} ∈ (see section 1) and γ_{0}, …, γ_{t−1} can be represented as the rational functions in (Z, Y) ∈ Ũ^{(l)}, we conclude taking into account the irreducibility of U^{(l)} that γ_{0}, …, γ_{t−1} are constants on Ũ^{(l)}. Thus, the exponent vectors I (see section 1) are the same for all the points (Z, Y) ∈ Ũ^{(l)}.

So, for (Z, Y) ∈ Ũ^{(l)} one can write t-sparse representation of the polynomial

g = ∑_{I} C_{I}(Z, Y)(Z^{−1}(X − Y))^{I}  (1)

where the coefficients C_{I}(Z, Y) depend on Z, Y. The equality (1) is equivalent to a system of equalities

g(ZX^{(0)} + Y) = ∑_{I} C_{I}(Z, Y)(Z^{−1}(X^{(0)} − Y))^{I}

where X^{(0)} runs over all the vectors from {0, …, d}^{n}. Adding to the latter system the system det Z ≠ 0, h_{1}^{(l)} = … = h_{N(l)}^{(l)} = 0 determining Ũ^{(l)} we come to a parametrical (with the parameters {Z_{ij}, Y_{i}}) linear in C_{I} system which one can solve invoking the algorithm from [H 83] (see also [CG 84]) in time M^{O(1)}d^{O(n^{4})}. This algorithm yields some disjoint decomposition of Ũ^{(l)} = ⋃_{S} U_{S}^{(l)} where each

U_{S}^{(l)} is a constructive set and also yields the rational functions C̄_{I,S}^{(l)}({Z_{ij}, Y_{i}}) ∈ ({Z_{ij}, Y_{i}}) such that C_{I} = C̄_{I,S}^{(l)}({Z_{ij}, Y_{i}}) for every point {Z_{ij}, Y_{i}} ∈ U_{S}^{(l)} (thus each C_{I} is a piecewise-rational function on Ũ^{(l)}).

The algorithm yields also polynomials h_{S,0}^{(l)}, …, h_{S,N_{S}^{(l)}}^{(l)} ∈ [{Z_{ij}, Y_{i}}] such

that U_{S}^{(l)} = {h_{S,0}^{(l)} ≠ 0, h_{S,1}^{(l)} = … = h_{S,N_{S}^{(l)}}^{(l)} = 0}. ¿From [H 83] (see also [CG 84])

we get the bounds on the degrees deg(h_{S,q}^{(l)}), deg(C̄_{I,S}^{(l)}) ≤ d^{O(n^{2})} and the bound M^{O(1)}d^{O(n^{2})} for the bit-size of every (rational) coefficients of all the yielded rational functions.

Thus, we have proved the following theorem (cf. proposition above).

Theorem. There is an algorithm which finds a minimal t and produces a constructive set U ⊂ ^{ n̄^{2}+n} of all {Z_{ij}, Y_{i}}_{1≤i,j≤n} such that g(ZX + Y) is t-sparse, in the form U = ⋃_{l} U^{(l)} and for each constructive set U^{(l)} the algorithm

produces polynomials H_{0}^{(l)}, …, H_{N^{(l)}}^{(l)} ∈ [{Z_{ij}, Y_{i}}] such that U^{(l)} = {H_{0}^{(l)} ≠ 0, H_{1}^{(l)} = … = H_{N^{(l)}}^{(l)} = 0}. Also the algorithm produces t exponent vectors and for each exponent vector I a rational function C_{I}^{(l)}({Z_{ij}, Y_{i}}) ∈ ({Z_{ij}, Y_{i}}) which provide t-sparse representations of

g = ∑_{I} C_{I}^{(l)}({Z_{ij}, Y_{i}})(Z^{−1}(X − Y))^{I}

which is valid for every point ({Z_{ij}, Y_{i}}) ∈ U^{(l)}. The degrees of all produced rational functions H_{S}^{(l)}, C_{I}^{(l)} do not exceed d^{O(n^{2})}, the bit-size of the coefficients of these rational functions can be bounded by (Md^{n^{2}})^{O(1)} and the running time of the algorithm is at most (Md^{n^{4}})^{O(1)}.

Again when Z_{ij}, Y_{i} belong to we could write down a polynomial system on Z, Y with a less number of equations. For this purpose we need the following Lemma 5. If g is a shifted t-sparse polynomial, then for any Z_{0}, Y_{0} such that det Z_{0} ≠ 0 for at least one of X_{1}^{(0)} = 1, …, n^{O(n)}2^{O(t^{4})}, a polynomial W_{g}(X_{1}^{(0)}, X_{2}, …, X_{n}, Y_{0}, Z_{0}) ∈ [X_{2}, …, X_{n}] does not vanish identically, provided that W_{g}(X, Y_{0}, Z_{0}) ∈ [X] does not vanish identically. Proof. Let for some Z^{(0)}, Y^{(0)} a polynomial g(Z^{(0)}X + Y^{(0)}) be t-sparse, i.e.

g = ∑_{J} β_{J} ∏_{1≤i≤n}((Z^{(0)})^{−1}(X − Y^{(0)}))_{i}^{j_{i}}

where J = (j_{1}, …, j_{n}) and the sum has at most t items (by ((Z^{(0)})^{−1}(X −Y^{(0)}))_{i} we denote i-th coordinate of the vector (Z^{(0)})^{−1}(X − Y^{(0)})). Then

(D_{n}^{K}g)(X, Y_{0}, Z_{0}) = ∑_{J} β_{J} ∏_{1≤i≤n}((Z^{(0)})^{−1}((Z_{0}P^{K}Z_{0}^{−1}(X−Y_{0})+Y_{0})−Y^{(0)}))_{i}^{j_{i}} for 0 ≤ K ≤ 2t.

Thus W_{g}(X, Y_{0}, Z_{0}) is a polynomial in (2t + 1)t products of the form like in the latter expression and these products can be considered as the elements of a Pfaffian chain. [Kh 91] entails (cf. also [GKS 93]) that the sum of Betti numbers of the variety {W_{g}(X, Y_{0}, Z_{0}) = 0} ⊂ ^{n} is less than n^{O(n)}2^{O(t^{4})}. As in particular (n − 1)-th Betti number b^{n−1} < n^{O(n)}2^{O(t^{4})} we conclude the statement of the lemma (cf. [GKS 93]).

Thus, Y, Z satisfy the conditions of lemma 4 if and only if det Z ≠ 0 and they satisfy the following n^{O(n^{2})}2^{O(nt^{4})} equations.

W_{g}(X_{1}^{(0)}, …, X_{n}^{(0)}, Y, Z) = 0, X_{1}^{(o)}, …, X_{n}^{(0)} ∈ {1, …, n^{O(n)}2^{O(t^{4})}}

4 Zero-test for shifted sparse polynomials

Let g be shifted t-sparse polynomial. Then (see lemma 5) for at least one of X_{1}^{(0)} = 1, …, n^{O(n)}2^{(t^{2})} a polynomial g(X_{1}^{(0)}, X_{2}, …, X_{n}) ∈ [X_{2}, …, X_{n}] does not vanish identically. Thus for zero-test one can compute g(X_{1}^{(0)}, …, X_{n}^{(0)}) for n^{O(n^{2})}2^{O(nt^{2})} points (X_{1}^{(0)}, …, X_{n}^{(0)}) ∈ {1, …, n^{O(n)}2^{O(t^{2})}}^{n}. Then g vanishes identically if and only if all the results of computation vanish. Thus, the complexity of zero-test does not depend on d.

Acknowledgement. The authors would like to thank C. Schnorr for initiating the question about the shifted sparse polynomials.

References

[BT 88] Ben-Or, M. & Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, Proc. 20 STOC ACM, 1988, pp. 301-309.

[CG 83] Chistov, A. & Grigoriev, D., Subexponential-time solving systems of

algebraic equations, Preprints LOMI E-9-83, E-10-83, Leningrad, 1983.

[CG 84] Chistov, A. & Grigoriev, D., Complexity of quantifier elimination in the theory of algebraically closed fields, Lect. Notes Comp. Sci. 176, 1984, pp. 17-31.

[GK 87] Grigoriev, D. & Karpinski, M., The matching problem for bipartite graphs with polynomially bounded permanents is in NC, Proc. 28 FOCS IEEE, 1987, pp. 166-172.

[GKS 90] Grigoriev, D., Karpinski, M. & Singer, M., Fast parallel algorithms for sparse multivariate polynimial interpolation over finite fields, SIAM J. Comput. 19, N 6, 1990, pp. 1059-1063.

[GKS 91] Grigoriev, D., Karpinski, M. & Singer, M., The interpolation problem for k-sparse sums of eigenfunctions of operators, Adv. Appl. Math. 12, 1991, pp. 76-81.

[GKS 92] Grigoriev, D., Karpinski, M. & Singer, M., Computational complexity

of sparse rational interpolation , to appear in SIAM J. Comput.

[GKS 93] Grigoriev, D., Karpinski, M. & Singer, M., Computational complexity of sparse real algebraic function interpolation, to appear in Proc. Int. Conf. Eff. Meth. Alg. Geom., Nice, April 1992 (Progr. in Math. Birkhäuser).

[H 83] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theor. Comp. Sci. 24, 1983, pp. 239-278.

[Ka 89] Karpinski, M., Boolean Circuit Complexity of Algebraic Interpolation Problems, Technical Report TR-89-027, International Computer Science Institute, Berkeley, 1989; in Proc. CSL’88, Lecture Notes in Computer Science 385, 1989, pp. 138-147.

[Kh 91] Khovanski, A., Fewnomials, Transl. Math. Monogr., AMS 88, 1991. [KY 88] Kaltofen, E. & Yagati, L., Improved sparse multivariate interpolation,

Report 88-17, Dept. Comput. Sci., Rensselaer Polytechnic Institute, 1988.

This article was processed using the LaTEX macro package with LLNCS style