Computational Complexity of Sparse Rational

Interpolation^{1}

Dima Grigoriev ^{2}

Dept. of Computer Science University of Bonn 5300 Bonn 1

and

Steklov Mathematical Institute Fontanka 27, St. Petersburg 191011 Russia

Marek Karpinski ^{3}

Dept. of Computer Science University of Bonn 5300 Bonn 1

and

International Computer Science Institute Berkeley, California

Michael F. Singer ^{4}

Dept. of Mathematics North Carolina State University Raleigh, NC 27695-8205

Abstract We analyse the computational complexity of sparse rational interpolation, and

give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic operations.

1A preliminary version of this paper has appeared in [10] 2The first author would like to thank the Max Planck Institute in Bonn for its hospitality and support

during the preparation of this paper.

3Supported 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.

4The third author would like to thank the University of Bonn for its hospitality and support during the preparation of this paper.

Introduction

In this paper we present an algorithm which, given a black box to evaluate a t-sparse (a quotient of two t-sparse polynomials) n-variable rational function f with integer coefficients, can find the coefficients and exponents appearing in a t-sparse representation of f using (t^{(nt)} log d)^{O(1)} black box evaluations and arithmetic operations and with arithmetic depth (nt log d)^{O(1)}, where d denotes the degree of t-sparse representation of f (see the Theorem at the end of section 4 for an exact statement of this result). Although these bounds involve the size of the exponents, this dependency only arises at the end of our algorithm. The algorithm genuinely produces (that is produces in a way whose arithmetic complexity does not depend on the size of the coefficients of f or on the degree of f, [19]) a polynomial whose roots are p-powers (for some small p) of the exponents appearing in a t-sparse representation of f. All known algorithms to find the roots of this polynomial (even knowing that they are p-powers) have complexity that depend on the size of the roots. This dependency also occurs in algorithms for interpolating t-sparse polynomials (c.f.,[1]) for the same reason.

To find the exponents appearing in some t-sparse representation of a t-sparse univariate rational function f(X) we proceed as follows: We consider representations of f(X) of the form (Σ_{i=1}^{t}a_{i}X^{α_{i}})/(Σ_{i=1}^{t}b_{i}X^{β_{i}}), where a_{i}, b_{i}, α_{i}, β_{i} are real numbers. Such a function is called a real quasirational function. Furthermore, we call such a representation minimal if it has a minimal number of nonzero terms in the numerator and denominator and is called normalized if some term is 1. We show that there are only a finite number of minimal normalized representations and that the exponents must be integers. We are able to produce a system T of polynomial equalities and inequalities (whose coefficients depend on the values of f(X) at t^{O(t)} points) that determine all the possible values of any such α_{i} and β_{i}. Using the methods of [13], we can then find all α_{i} and β_{i}. To find the exponents when f(X_{1}, …, X_{n}) is a multivariate polynomial, we show how to produce sufficiently many n-tuples of integers (ν_{1}, …, ν_{n}) such that the exponents of f can be recovered from the exponents of all the f(X^{ν_{1}}, …, X^{ν_{n}}).

Complexity issues for t-sparse polynomial and rational function interpolation have been dealt with in several papers. Polynomial (black box) interpolation was studied in [1],[2],[9],[12],[17], [19],[27], [28]. For bounded degree rational interpolation (when the bound on the degree is part of the input) see [15],[16],[25]. Approximative unbound interpolation arises also naturally in issues of computational learnability of sparse rational functions (cf. [21]). The present authors have previously studied the problem of interpolation of rational functions in [10], but the algorithm presented there for finding the exponents had considerably worse complexity. The present paper significantly improves the results of that paper by introducing the notion of a minimal representation (allowing us to directly compute a finite set of possible exponents instead of just bounding them) and a new technique for reducing multivariate interpolation to univariate interpolation. As we shall see these ideas give us a more efficient algorithm.

The rest of the paper is organized as follows: In Section 1 we give formal definitions of a quasirational function and related concepts and prove some basic facts about these functions. In Section 2 we introduce some useful linear operators on fields of these functions. We use these operators to derive criteria for a function to be t-sparse. In Section 3 we use these criteria to give an algorithm for t-sparse univariate interpolation. In Section 4, we again use these operators to show how multivariate interpolation can be reduced to univariate interpolation. Complexity analyses of the algorithms are also given in Sections 3 and 4.

1 Quasirational Functions

A finite sum

∑_{I} c_{I}X^{I}  (1)

where I = (α_{1}, …, α_{n}), α_{i} ∈ C , X^{I} = X^{α_{1}} · . . . · X^{α_{n}}, c_{I} ∈ C is called a quasipolynomial of n variables. The set of quasipolynomials forms a ring under the obvious operations and we denote this ring by C ⟨X_{1}, …, X_{n}⟩. The subring of quasipolynomials (1) with α_{i} ∈ IR and c_{I} ∈ IR will be referred to as the ring of real quasipolynomials and will be denoted by IR⟨X_{1}, …, X_{n}⟩. A ratio of two quasipolynomials (real quasipolynomials) is called a quasirational function (real quasirational function). The set of such functions forms a field that we denote by C ⟨⟨X_{1}, …, X_{n}⟩⟩ (IR⟨⟨X_{1}, …, X_{n}⟩⟩). Note that Q (X_{1}, …, X_{n}) ⊂ IR⟨⟨X_{1}, …, X_{n}⟩⟩. We use the expressions “polynomial” or “rational function” in the usual sense, that is for a quasipolynomial or quasirational function with non-negative integer exponents in their terms.

We say that the quasipolynomial (1) is t-sparse if at most t of the c_{I} are nonzero. If a quasirational function f can be written as a quotient of a numerator that is t_{1}-sparse and a denominator that is t_{2}-sparse then we say that f is (t_{1}, t_{2})-sparse. For example, (X^{m} − 1)/(X − 1) = X^{m−1} + ⋯ + 1 is (2, 2)-sparse and also (m, 1)-sparse. If f is (t_{1}, t_{2})- sparse but not (t_{1} − 1, t_{2})- or (t_{1}, t_{2} − 1)-sparse, we say that f is minimally (t_{1}, t_{2})-sparse. Note that the above example is both minimally (2, 2)-sparse and minimally (m, 1)-sparse. We say that a representation f = p/q is a minimal (t_{1}, t_{2})-sparse representation if f is minimally (t_{1}, t_{2})-sparse and p is t_{1}-sparse and q is t_{2}-sparse.

We will need a zero test for (t_{1}, t_{2})-sparse rational functions. This is similar to the well known zero test for t-sparse polynomials (c.f., [1],[9],[11]). We assume that we are given a black box for an n-variable rational function f with integer coefficients in which we can put points with rational coefficients. The output of the black box is either the value of the function at this point or some special sign, e.g., “∞”, if the denominator of the irreducible representation of the function vanishes at this point (a representation f = g/h, g, h ∈ C [X_{1}, …, X_{n}], is irreducible if g and h are relatively prime).

Lemma 1. Let f be a (t_{1}, t_{2})-sparse rational function of n variables, let p_{1}, …, p_{n} be n distinct primes and let P^{j} = (p_{1}^{j}, …, p_{n}^{j}) 1 ≤ j ≤ t_{1} + t_{2} − 1. Then f is not identically zero if and only if the black box outputs a number different from 0 and ∞ at one of the points P^{j}.

Proof. Recall that if M_{1}, …, M_{t} are distinct positive numbers then any t×t subdeterminant of the r ×t matrix (M_{s}^{j})_{1≤s≤t, 1≤j≤r} is non-singular (c.f., [5]). Since the black box gives output based on an irreducible representation of f, we see that any zero of the denominator of such a representation is zero of the denominator of a (t_{1}, t_{2})-sparse representation of f. Using the remark about the matrix (M_{s}^{j}) above we see that the denominator can vanish at, at most, t_{2} − 1 of these points. A similar argument applies to the numerator. Therefore, the (t_{1}, t_{2})-sparse function f is not identically zero if and only if the black box outputs a number different from 0 and ∞ at one of these points P^{j}.

We note that Lemma 1 is not true for quasirational functions. For example, let p = 2 and f(X) = 1 − X^{\frac{2π\sqrt{−1}}{log 2}} . We then have that f(2^{i}) = 0 for all i. If one restricts oneself to real quasirational functions, then Lemma 1 is also not true for n ≥ 2. To see this, let f(X_{1}, X_{2}) = X_{1}^{log_{2} 5} − X_{2}^{log_{3} 5} and p_{1} = 2, p_{2} = 3. However, we do have a zero test for univariate real quasirational functions. We will only need such a test for real quasipolynomials which we state in the following lemma.

Lemma 2. Let p be a positive real number and let f ∈ IR⟨X⟩ be t-sparse. If f(p^{i}) = 0 for i = 0, …, t − 1, then f ≡ 0.

Proof. Let f = Σ_{i=1}^{t}a_{i}X^{α_{i}} where α_{i} ≠ α_{j} for i ≠ j. Since f(p^{i}) = 0 for i = 0, …, t − 1 then

[ \begin{matrix}1 & ⋯ & 1 \\ p^{α_{1}} & ⋯ & p^{α_{t}} \\ ⋮ & ⋮ & ⋮ \\ (p^{α_{1}})^{t−1} & & (p^{α_{t}})^{t−1} \end{matrix} ] [ a_{1} ; a_{2} ; ⋮ ; a_{t} ] = [ 0 0 ⋮ 0 ]

Since the α_{i} are real, p^{α_{i}} ≠ p^{α_{j}} if i ≠ j. Therefore the above t × t matrix is non-singular and so a_{1} = … = a_{t} = 0.

If f is a quasirational function, we call a representation f = g/h, g, h ∈ C ⟨X_{1}, …, X_{n}⟩ normalized if g or h contains the constant term 1. For an arbitrary representation f = g̃/h̃, there are a finite number of monomials M such that (g̃/M)/(h̃/M) is normalized.

Lemma 3. a) Assume p/q = p̄/q̄ are normalized representations of a multivariate quasirational function and assume that p/q is a minimal (t_{1}, t_{2})-sparse representation. Then the ZZ-module generated by the exponent vectors of p and q is a submodule of the ZZ-module generated by the exponent vectors of p̄ and q̄.

b) There exist at most (t_{1} + t_{2})^{O(t_{1}+t_{2})} minimal (t_{1}, t_{2})-sparse representations. Furthermore, for given exponent vectors, the coefficients in the corresponding minimal representation are unique.

c) Assume the same conventions as in a). Then

max{| deg(p)|, | deg(q)|} ≤ 2(t_{1} + t_{2}) max{| deg(p̄)|, | deg(q̄)|}.

Proof. Let I_{1}, …, I_{t_{1}} be the exponent vectors of p, J_{1}, …, J_{t_{2}} be the exponent vectors of q and let {Ī_{i}} (respectively {J̄_{j}}) be the exponent vectors of p̄ (respectively q̄). We define a weighted directed graph G in the following way. The vertices of G correspond to the t_{1} + t_{2} exponents of p/q. We join I_{i} and J_{j} if I_{i} +J̄_{j_{1}} = J_{j} +Ī_{i_{1}} for some i_{1}, j_{1} and assign the weight Ī_{i_{1}} − J̄_{j_{1}} to the edge (I_{i}, J_{j}). We join I_{i} and I_{i_{1}} if I_{i} + J̄_{j} = I_{i_{1}} + J̄_{j_{1}} for some j ≠ j_{1} and assign weight J̄_{j_{1}} − J̄_{j} to the edge (I_{i}, I_{i_{1}}). Finally, we join J_{j} and J_{j_{1}} if J_{j} + Ī_{i} = J_{j_{1}} + Ī_{i_{1}} for some i ≠ i_{1} and assign weight Ī_{i_{1}} − Ī_{i} to the edge (J_{j}, J_{j_{1}}).

We claim that G is connected. If not, let G_{o} be the connected component which contains the exponent vector (0, …, 0). One sees that the representation p_{o}/q_{o} obtained from p/q by deleting all terms with exponent vectors not belonging to this connected component equals p̄/q̄. This contradicts the minimality of p/q and proves the claim.

To prove a) and c), consider a spanning tree T of G and let (0, …, 0) be the root of T . Any exponent vector I_{i} (respectively J_{i}) equals the sum of the weights along the unique path connecting I_{i} (respectively J_{i}) with the root and so lies in the module generated by the Ī_{i} and J̄_{i}.

To prove b), note that the spanning tree above uniquely determines the set of exponent vectors that can occur in p/q. Therefore the number of exponent vectors in the numerator and denominator is at most the product of the number of such weighted trees and ( \begin{matrix}t_{1} + t_{2} \\ t_{1} \end{matrix} ) (the latter value being the number of choices of exponents for the numerator and denominator). The number of rooted trees with (t_{1} + t_{2}) vertices is at most (t_{1} + t_{2})^{0(t_{1}+t_{2})}. For a fixed tree, the number of ways to assign weights of the above form from a fixed set \left\{{ \atop Ī_{i}}\right\}_{i=1}^{t_{1}} ∪ \{J̄_{j}\}_{j=1}^{t_{2}} can be bounded by (t_{1} + t_{2})^{0(t_{1}+t_{2})}. Thus the number of exponent vectors can also be bounded by (t_{1} + t_{2})^{0(t_{1}+t_{2})}.

We now prove the last statement of b). Assume that p_{o}/q_{o} = p/q are two different minimal (t_{1}, t_{2})-sparse representations with the same exponent vectors in the corresponding numerators and denominators. For suitable c ∈ C , \frac{p_{o} − cp}{q_{o} − cq} = \frac{p}{q} is a representation that is either (t_{1} − 1, t_{2})- or (t_{1}, t_{2} − 1)-sparse, contradicting the minimality of (t_{1}, t_{2}). This completes the proof of Lemma 3.

We have the following immediate consequence of Lemma 3 a).

Corollary 4. Any normalized minimal (t_{1}, t_{2})-sparse quasi-rational representation of a rational function has exponents that are integers.

2 Linear Operators

In the following sections it will be useful to consider the actions of certain linear operators on fields of quasirational functions.

Definition. a) Let p_{1}, … p_{n} be distinct prime numbers and let D_{n} : C ⟨⟨X_{1}, …, X_{n}⟩⟩ → C ⟨⟨X_{1}, …, X_{n}⟩⟩ be the C -linear operator defined by D_{n}(X_{i}^{α}) = p_{i}^{α}X_{i}^{α}, where the number p_{i}^{α} is defined to be e^{α log p_{i}} for some fixed branch of the logarithm. When n = 1 we will write C ⟨⟨X⟩⟩ instead of C ⟨⟨X_{1}⟩⟩ and D instead of D_{1}.

b) Let 𝔇 : C ⟨⟨X⟩⟩ → C ⟨⟨X⟩⟩ be the C -linear operator defined by

𝔇(X^{α}) = X \frac{d}{dX} (X^{α}) = αX^{α}.

Note that D_{n} is a homomorphism, i.e. D_{n}(fg) = D_{n}(f)D_{n}(g) while 𝔇 is a derivation, i.e. 𝔇(fg) = 𝔇(f)g + f𝔇(g). This difference will force us to deal with these operators separately. We begin by studying D_{n}.

Lemma 5. a) Let f ∈ C (X_{1}, …, X_{n}) and assume that D_{n}(f) = f. Then f ∈ C . b) Let f ∈ IR⟨⟨X⟩⟩ and assume that D(f) = f. Then f ∈ IR.

Proof. a) If D_{n}(f) = f, then f(X_{1}, …, X_{n}) = f(p_{1}X_{1}, …, p_{n}X_{n}) = f(p_{1}^{2}X_{1}, …, p_{n}^{2}X_{n}) = · · · . Lemma 1 implies that f(X_{1}, …, X_{n}) = f(X_{1}Y_{1}, …, X_{n}Y_{n}) for new variables Y_{1}, …, Y_{n}. If f = g/h, let g = ∑_{I} a_{I}X^{I}, h = ∑_{J} b_{J}X^{J}. Comparing coefficients of the corresponding monomials in X and Y we have that, after a suitable re-ordering, I_{1} = J_{1}, I_{2} = J_{2}, … and a_{I}b_{J} = a_{J}b_{I} for all I, J. Therefore f ∈ C .

b) The proof is the same as in a) using Lemma 2 instead of Lemma 1.

Note that Lemma 5 a) is not true for f ∈ IR⟨⟨X_{1}, …, X_{n}⟩⟩ ⊂ C ⟨⟨X_{1}, …, X_{n}⟩⟩, n ≥ 2. To see this let f = X_{1}^{log_{2} 5}X_{2}^{− log_{3} 5}, p_{1} = 2, p_{2} = 3. Lemma 5 b) is not true for f ∈ C ⟨⟨X⟩⟩ since, for p = 2, f = X^{\frac{2π\sqrt{−1}}{log 2}} gives a counterexample.

Lemma 6. a) If y_{1}, …, y_{m} ∈ C (X_{1}, …, X_{n}) then y_{1}, …, y_{m} are linearly dependent over C if and only if

W_{D_{n}}(y_{1}, …, y_{m}) = det [ \begin{matrix}y_{1} & ⋯ & y_{m} \\ D_{n}y_{1} & ⋯ & D_{n}y_{m} \\ ⋮ & ⋮ & ⋮ \\ D_{n}^{m−1}y_{1} & ⋯ & D_{n}^{m−1}y_{m} \end{matrix} ] = 0

b) If y_{1}, …, y_{m} ∈ IR⟨⟨X⟩⟩, then y_{1}, …, y_{m} are linearly dependent over IR if and only if W_{D_{1}}(y_{1}, …, y_{m}) = 0.

Proof. a) If y_{1}, …, y_{m} are linearly dependent over C then we clearly have W_{D_{n}}(y_{1}, …, y_{m}) = 0. Now assume that W_{D_{n}}(y_{1}, …, y_{m}) = 0. In this case there exist f_{1}, …, f_{m} ∈ C (X_{1}, …, X_{n}), not all zero, such that

f_{1}y_{1} + … + f_{m}y_{m} = f_{1}D_{n}y_{1} + … + f_{m}D_{n}y_{m} = … = f_{1}D_{n}^{m−1}y_{1} + … + f_{m}D_{n}^{m−1}y_{m} = 0

We may assume f_{1} = 1. Applying D_{n} to each of these equations, we have

D_{n}^{i}y_{1} + D_{n}f_{2}D^{i}y_{2} + … + D_{n}f_{n}D_{n}^{i}y_{m} = 0

for i = 1, …, n. This implies that

(f_{2} − D_{n}f_{2})D_{n}^{i}y_{2} + … + (f_{m} − D_{n}f_{m})D_{n}^{i}y_{m} = 0

for i = 1, …, n − 1. Either f_{i} − D_{n}f_{i} = 0 for i = 2, …, m, in which case we are done by Lemma 5, or by induction there exist α_{2}, …, α_{m} ∈ C , not all zero, such that α_{2}D_{n}y_{2} + … + α_{m}D_{n}y_{m} = 0. Therefore D_{n}(α_{2}y_{2} + … + α_{m}y_{m}) = 0 so α_{2}y_{+} … + α_{m}y_{m} = 0. The proof of part b) is similar and omitted.

Lemma 6 immediately implies the following criterion for a real quasirational function to be (t_{1}, t_{2})-sparse.

Lemma 7 a) Let f ∈ C (X_{1}, …, X_{n}), f is (t_{1}, t_{2})-sparse if and only if there exist I_{1}, …, I_{t_{1}}, J_{1}, …, J_{t_{2}} ∈ ZZ^{n}, I_{i} ≠ I_{j}, J_{i} ≠ J_{j} for i ≠ j such that W_{D_{n}}(X^{I_{1}}, …, X^{I_{t_{1}}}, X^{J_{1}}f, …, X^{J_{t_{2}}}f) = 0.

b) Let f ∈ IR⟨⟨X⟩⟩. f is (t_{1}, t_{2})-sparse if and only if there exist α_{1}, …, α_{t_{1}}, β_{1}, …, β_{t_{2}} ∈ IR, α_{i} ≠ α_{j}, β_{i} ≠ β_{j} for i ≠ j such that W_{D}(X^{α_{1}}, …, X^{α_{t_{1}}}, X^{β_{1}}f, …, X^{β_{t_{2}}}f) = 0.

Proof. a) f is (t_{1}, t_{2})-sparse if and only if there exist I_{1}, …, I_{t_{1}}, J_{1}, …, J_{t_{2}} ∈ ZZ^{n}, I_{i} ≠ I_{j}, J_{i} ≠ J_{j} for i ≠ j and a_{1}, …, a_{t_{1}}, b_{1}, …, b_{t_{2}} ∈ C , not all zero, such that ∑_{i=1}^{t_{1}} a_{i}X^{I_{i}} + ∑_{j=1}^{t_{2}} b_{j}X^{I_{j}}f = 0. By Lemma 6 this happens if and only if W_{D_{n}}(X^{I_{1}}, …, X^{I_{t_{1}}}, X^{J_{1}}f, …, X^{J_{t_{2}}}f) = 0.

The proof of b) is similar.

We now consider the other linear operator 𝔇 on C ⟨⟨X⟩⟩. We will need results similar to Lemmas 5 and 6.

Lemma 8. If f ∈ C ⟨⟨X⟩⟩ and 𝔇f = 0 then f ∈ C .

Proof. First assume that f = ∑_{i=1}^{t} a_{i}X^{α_{i}} ∈ C ⟨X⟩. If 0 = 𝔇f = ∑_{i=1}^{t} a_{i}α_{i}X^{α_{i}}, then t = 1 and a_{1} = 0, so f ∈ C .

Now let f ∈ C ⟨⟨X⟩⟩. f is minimally (t_{1}, t_{2})-sparse for some (t_{1}, t_{2}). Let f = g/h be a minimal (t_{1}, t_{2})-sparse normalized representation. If 𝔇h = 0, then we have just shown that h ∈ C . Since 𝔇f = ((𝔇g)h − g𝔇h)/h^{2} = (𝔇g)/h, so 𝔇g = 0. Therefore g ∈ C and so f ∈ C . We will therefore now assume 𝔇h ≠ 0 and derive a contradiction. Since (𝔇g)h − g𝔇h = 0, we have g/h = 𝔇g/𝔇h. Since g/h is normalized, 𝔇g/𝔇h is a (t_{1} − 1, t_{2})- or a (t_{1}, t_{2} − 1)-sparse representation of f, a contradiction.

Lemma 9. If y_{1}, …, y_{m} ∈ C ⟨⟨X⟩⟩ then y_{1}, …, y_{m} are linearly dependent over C if and only if

W_{𝔇}(y_{1}, …, y_{m}) = det [ \begin{matrix}y_{1} & ⋯ & y_{m} \\ 𝔇y_{1} & ⋯ & 𝔇y_{m} \\ ⋮ & ⋮ & ⋮ \\ 𝔇^{m−1}y_{1} & ⋯ & 𝔇^{m−1}y_{m} \end{matrix} ] = 0

Proof. Lemma 8 implies that C ⟨⟨X⟩⟩ is a differential field with constant subfield equal to C . The result now follows from ([18], Theorem 3.7).

3 Univariate Interpolation

Lemma 7 in the previous section allows us to characterize (t_{1}, t_{2})-sparse rational functions and is the basis of the following algorithm for finding the exponents of a sparse univariate rational function.

Assume we are given a black box to evaluate a univariate rational function f ∈ Q (X) and assume we are told that it is minimally (t_{1}, t_{2})-sparse (the general case when we are only told it is (t_{1}, t_{2})-sparse is handled below). Consider the expression

S(p^{α_{1}}, …, p^{α_{t_{1}}}, p^{β_{1}}, …, p^{β_{t_{2}}}, f(X), f(pX), …, f(p^{t_{1}+t_{2}−1}X))

= \frac{W_{D}(X^{α_{1}}, …, X^{α_{t_{1}}}, X^{β_{1}}f, …, X^{β_{t_{2}}}f)}{X^{α_{1}} · . . . · X^{α_{t_{1}}} · X^{β_{1}} · . . . · X^{β_{t_{2}}}}

Note that S is a polynomial in the indicated terms with integer coefficients. Replacing p^{α_{1}}, …, p^{α_{t_{1}}}, p^{β_{1}}, …, p^{β_{t_{2}}} with new variables Y_{1}, …, Y_{t_{1}+t_{2}} we get a polynomial S(Y_{1}, …, Y_{t_{1}+t_{2}}, f(X), f(pX), …, f(p^{t_{1}+t_{2}−1}X)) with at most (t_{1} + t_{2})^{t_{1}+t_{2}} terms in the variables Y_{1}, …, Y_{t_{1}+t_{2}} and multilinear in the black boxes f(X), f(pX), …, f(p^{t_{1}+t_{2}−1}X).

Since we are looking for the exponents of a normalized minimal (t_{1}, t_{2})-sparse representation of f, we may assume Y_{1} = 1. By lemma 7b) (0, α_{2}, …, α_{t_{1}}, β_{1}, … β_{t_{2}}) ∈ IR^{(t_{1}+t_{2})} will be a vector of such exponents if and only if

S(1, p^{α_{2}}, …, p^{α_{t_{1}}}, p^{β_{1}}, …, p^{β_{t_{2}}}, f(X), f(pX), …) = 0  (2)
0 ≠ α_{i} ≠ α_{j}, β_{i} ≠ β_{j} for i ≠ j  (3)

Observe that S as a rational function from IR(X) is ((t_{1} + t_{2})^{2(t_{1}+t_{2})}, t_{2}^{t_{1}+t_{2}})-sparse, hence by lemma 1 condition (2) is equivalent to the condition that S is either ∞ or 0 for X = p^{i}, i = 0, …, 2(t_{1} + t_{2} + 1)^{2(t_{1}+t_{2})} − 1. For at least (t_{1} + t_{2} + 1)^{2(t_{1}+t_{2})} of these points (being independent from α_{2}, ⋯, β_{t_{2}}), S will be zero. Using the black box for f(X), we can determine a system T consisting of (t_{1} + t_{2} + 1)^{2(t_{1}+t_{2})} equations in the unknowns Y_{2}, …, Y_{t_{1}+t_{2}} of degree at most (t_{1} + t_{2})^{2}, of inequalities 1 ≠ Y_{i} ≠ Y_{j} ≠ 1, 2 ≤ i < j ≤ t_{1}, Y_{i} ≠ Y_{j}, t_{1} < i < j ≤ t_{1} + t_{2} and of inequalities Y_{2} ≥ 1, ⋯, Y_{t_{1}+t_{2}} ≥ 1 that is equivalent to (2),(3) (for Y_{2} = p^{α_{2}}, ⋯, Y_{t_{1}+t_{2}} = p^{β_{t_{2}}}). By Lemma 3 b), T has a finite number of solutions in IR^{t_{1}+t_{2}−1}. Note that Corollary 4 implies that these solutions are integers. We can apply the algorithm of [13], [14] (cf. also [1]) to this system and find these solutions with ((t_{1} + t_{2})^{(t_{1}+t_{2})} log d)^{O(1)} arithmetic operations and depth ((t_{1} + t_{2}) log d)^{O(1)}, where d is the maximum of the exponents α_{2}, …, β_{t_{2}}. Note that the algorithm of [13], [14] will yield a polynomial satisfied by these p-powers with (t_{1} + t_{2})^{O(t_{1}+t_{2})} arithmetic operations and (t_{1} + t_{2})^{O(1)} depth. As we noted in the introduction, the dependence on d of the final complexity is introduced when we find the roots of this polynomial. One can find these roots as in [23] or more simply by considering the powers of p that divide the coefficients. We remark that this algorithm also implies that there are at most (t_{1} + t_{2})^{0(t_{1}+t_{2})} solutions (cf. lemma 3b)) and that these solutions p^{α_{2}}, ⋯, p^{β_{t_{2}}} are bounded by p^{d} ≤ exp(M(t_{1} + t_{2})^{O(t_{1}+t_{2})}) where M is a bound on the bitsize of the values yielded by the black box when we evaluate f(p^{i+j}) for i = 0, …, t_{1} + t_{2} − 1, j = 0, …, 2(t_{1} + t_{2} + 1)^{2(t_{1}+t_{2})} − 1. Hence the exponents α_{2}, ⋯, β_{t_{2}} of the rational function f do not exceed d ≤ M(t_{1} + t_{2})^{O(t_{1}+t_{2})}. Notice that the algorithm can find the exponents α_{2}, ⋯, β_{t_{2}} in ((t_{1} + t_{2})^{(t_{1}+t_{2})} log d)^{O(1)} arithmetic operations with the depth ((t_{1} + t_{2}) log d)^{O(1)}.

We can find the coefficients by solving a system of linear equations gotten from

(∑_{i=1}^{t_{2}} b_{i}X^{β_{i}}) f(X) = ∑_{i=1}^{t_{1}} a_{i}X^{α_{i}}

by letting X = p^{j}, j = 0, 1, …, t_{1} + t_{2} − 1. Note that Lemma 3 b) implies that this system will have a unique solution. This can be found with (t_{1} + t_{2})^{0(1)} arithmetic operations with depth ((log(t_{1} + t_{2}))^{0(1)}, since to set up this system one has to compute powers p^{α_{i}}, p^{β_{j}} which were computed above.

Turning to the general case where we are only told that f is (t_{1}, t_{2})-sparse, we proceed as follows: We consider all pairs (t′_{1}, t′_{2}) with 1 ≤ t′_{1} ≤ t_{1}, 1 ≤ t′_{2} ≤ t_{2} and use the above algorithm for these pairs. The first time that the above algorithm yields a non-empty set of solutions, we are guaranteed that, for this (t′_{1}, t′_{2}), f has a minimal (t′_{1}, t′_{2})-sparse representation and that the algorithm has yielded the exponents and the coefficients.

4 Multivariate Interpolations

Let f(X_{1}, …, X_{n}) ∈ Q (X_{1}, ⋯, X_{n}) be a minimally (t_{1}, t_{2})-sparse rational function given by a black box. We shall show in this section how the problem of finding the exponent vectors of f can be reduced to the univariate case. In particular, we shall show that the set of vectors ν = (ν_{1}, …, ν_{n}) ∈ C^{n} such that fν(X) = f(X^{ν_{1}}, …, X^{ν_{n}}) is not minimally (t_{1}, t_{2})-sparse is a small set V. We will then show that if we find the exponents of fν for sufficiently many ν ∉ V, then we can recover the exponents appearing in f.

Lemma 10. Let f(X_{1}, …, X_{n}) be a minimally (t_{1}, t_{2})-sparse rational function and let ν_{1}, …, ν_{n} ∈ C be linearly independent over ZZ. Then f(X^{ν_{1}}, …, X^{ν_{n}}) is minimally (t_{1}, t_{2})- sparse.

Proof. Let p̃(X)/q̃(X) be a minimally (t̃_{1}, t̃_{2})-sparse representation of f(X^{ν_{1}}, …, X^{ν_{n}}) with t̃_{1} ≤ t_{1}, t̃_{2} ≤ t_{2}. By Lemma 3 a), we may assume that p̃, q̃ ∈ C [X^{ν_{1}}, …, X^{ν_{n}}]. Since the map sending X^{ν_{i}} to X_{i} induces an isomorphism of C (X^{ν_{1}}, …, X^{ν_{n}}) onto C (X_{1}, …, X_{n}), we get a (t̃_{1}, t̃_{2})-sparse representation of f(X_{1}, …, X_{n}). Therefore, t̃_{1} = t_{1}, t̃_{2} = t_{2}.

Lemma 11. Let f be a minimally (t_{1}, t_{2})-sparse rational function with integer coefficients. The set V of vectors ν ∈ C^{n} such that fν is not minimally (t_{1}, t_{2})-sparse lies in the union of at most (t_{1} + t_{2})^{0((t_{1}+t_{2})n)} hyperplanes determined by linear forms with integer coefficients.

Proof. We will first show that V is defined by a set of polynomial equalities and inequalities with coefficients in Q (i.e. V is a Q -constructible set). Let V_{1}, …, V_{n} be variables. We shall write down conditions on V_{1}, …, V_{n} so that f(X^{V_{1}}, …, X^{V_{n}}) is (t_{1} − 1, t_{2})- sparse, let these conditions determine a set 𝔚^{(1)} (similar conditions can be derived for f(X^{V_{1}}, …, X^{V_{n}}) to be (t_{1}, t_{2} − 1)-sparse, let these conditions determine a set 𝔚^{(2)}). Thus 𝔚 = 𝔚^{(1)} ∪ 𝔚^{(2)}. Lemma 9 implies that f(X^{V_{1}}, …, X^{V_{n}}) is (t_{1} − 1, t_{2})-sparse if and only if there exist α_{1}, …, α_{t_{1}−1}, β_{1}, … β_{t_{2}} ∈ C such that α_{i} ≠ α_{j}, β_{i} ≠ β_{j} for i ≠ j and

S_{𝔇} (α_{1}, …, α_{t_{1}−1}, β_{1}, …, β_{t_{2}}, f(X^{V_{1}}, …, X^{V_{n}}), …, 𝔇^{t_{1}+t_{2}−2}f(X^{V_{1}}, …, X^{V_{n}}))

= \frac{W_{𝔇}(X^{α_{1}}, …, X^{α_{t_{1}−1}}, X^{β_{1}}f(X^{V_{1}}, …, X^{V_{n}}), …, X^{β_{t_{2}}}f(X^{V_{1}}, …, X^{V_{n}}))}{X^{α_{1}} · . . . · X^{α_{t_{1}−1}} · X^{β_{1}} · . . . · X^{β_{t_{2}}}}

= 0  (4)

When we clear the denominator of (4) we will get a linear function in expressions of the form X^{Σa_{i}V_{i}} with coefficients C_{a}, where a = (a_{1}, ⋯, a_{n}) ∈ ZZ^{n}, that are polynomials in α_{1}, …, α_{t_{1}−1}, β_{1}, …, β_{t_{2}}, V_{1}, …, V_{n} with integer coefficients. Observe that there are at most (t_{1} + t_{2})^{0(t_{1}+t_{2})} distinct powers X^{Σa_{i}V_{i}} that can appear

For any pair Σa_{i}V_{i}, Σb_{i}V_{i} of distinct exponents, let L_{a,b} = Σ(a_{i} − b_{i})V_{i}. Lemma 9 states that for any choice (ν_{1}, …, ν_{n}) ∈ C^{n} such that L_{a,b}(ν_{1}, …, ν_{n}) ≠ 0, f is (t_{1} − 1, t_{2})-sparse if and only if there exist α_{1}, …, α_{t_{1}−1}, β_{1}, …, β_{t_{2}} ∈ C such that all the C_{a} considered above vanish. Let Φ be the formula, from the language of algebraically closed fields, with bound variables α_{1}, …, α_{t_{1}−1}, β_{1}, …, β_{t_{2}} and free variables V_{1}, …, V_{n} that expresses this latter statement. This formula contains at most (t_{1} + t_{2})^{0(t_{1}+t_{2})} polynomials, each of degree at most (t_{1} + t_{2})^{2}

Applying the results of [6] (see also [4]), we can eliminate quantifiers and get a quantifier free formula Ψ in variables V_{1}, …, V_{n} equivalent to Φ. Furthermore, the polynomials occurring in Ψ have degrees at most (t_{1}+t_{2})^{0((t_{1}+t_{2})n)} and there are at most (t_{1}+t_{2})^{0((t_{1}+t_{2})n)} of these. This formula determines a constructible set 𝔚_{0} ⊂ C^{n}. As it was shown above the symmetric difference (𝔚^{(1)} \ 𝔚_{0}) ∪ (𝔚_{0} \ 𝔚^{(1)}) lies in a union of all (t_{1} + t_{2})^{O(t_{1}+t_{2})} hyperplanes of the kind L_{a,b} for considered above integer vectors a, b. ¿From Lemma 10, we know that for each point (ν_{1}, …, ν_{n}) ∈ 𝔚 there exists a relation ∑_{i=1}^{n} γ_{i}ν_{i} = 0 for suitable integers γ_{1}, …, γ_{n} not all zero. ¿From Lemma 12 of the appendix we know that each irreducible component of 𝔚_{0} (and also of 𝔚) lies in a hyperplane. Therefore 𝔚 lies in the union of at most (t_{1} + t_{2})^{0((t_{1}+t_{2})n)} hyperplanes determined by linear forms with integer coefficients.

We now proceed to describe an algorithm to find p-powers of the exponents of a minimally (t_{1}, t_{2})-sparse normalized rational function f.

For any c > 0 using the construction from ([11] or [12], Lemma), one can explicitly produce, for suitable c_{1} > 0, c_{2} > 0, N = (t_{1} + t_{2})^{c_{1}(t_{1}+t_{2})n} vectors ν^{(i)} = (ν_{1}^{(i)}, …, ν_{n}^{(i)}), 1 ≤ i ≤ N where the integers 1 ≤ ν_{j}^{(i)} ≤ (t_{1} + t_{2})^{c_{2}(t_{1}+t_{2})n} such that for any family of (t_{1} + t_{2})^{c(t_{1}+t_{2})n} hyperplanes (containing the origin) at least n of these vectors lie in none of these hyperplanes and any n of these vectors are linearly independent. We take c > 0 such that the number of hyperplanes in lemma 11 is at most (t_{1} + t_{2})^{c(t_{1}+t_{2})n} (so for the algorithm we have only to estimate explicitely constant c once and forever) and apply to this c the construction mentioned above. For each of the vectors ν^{(i)} produced in this way, use the algorithm from Section 3 to find t_{1}^{(i)} ≤ t_{1}, t_{2}^{(i)} ≤ t_{2} such that the rational function f ν_{(i)} ∈ Q (X) has a minimal (t_{1}^{(i)}, t_{2}^{(i)})-sparse representation. By Lemma 11 and the construction of the ν^{(i)}, there exist at least n vectors among the ν^{(i)} (without loss of generality we let them be ν^{(1)}, …, ν^{(n)}) such that fν_{(i)} is minimally (t_{1}, t_{2})-sparse for all 1 ≤ i ≤ n. Using the algorithm from section 3 we find p-powers of the exponents of all normalized (t_{1}, t_{2})-sparse representations of fν_{(i)} for each 1 ≤ i ≤ n (recall that there are at most (t_{1} + t_{2})^{0(t_{1}+t_{2})} of these). For each fν_{(i)}, 1 ≤ i ≤ n, pick out one set of such p-powers of the exponents p^{α_{1}^{(i)}}, …, p^{α_{t_{1}}^{(i)}}, p^{β_{1}^{(i)}}, …, p^{β_{t_{2}}^{(i)}}. For each i, 1 ≤ i ≤ n, we also pick out two permutations π^{(i)} ∈ S_{t_{1}} and σ^{(i)} ∈ S_{t_{2}}, where S_{m} is the permutation group on m elements. For every j_{1}, 1 ≤ j_{1} ≤ t_{1}, the algorithm solves the p-power form of a linear system

p^{∑_{k=1}^{n} ν_{k}^{(i)}Y_{k}^{(j_{1})}} = p^{α_{π^{(i)}(j_{1})}^{(i)}}  (5)

1 ≤ i ≤ n and for every j_{2}, 1 ≤ j_{2} ≤ t_{2} a system

p^{∑_{k=1}^{n} ν_{k}^{(i)}Z_{k}^{(j_{2})}} = p^{β_{σ^{(i)}(j_{2})}^{(i)}}  (6)
1 ≤ i ≤ n

Using [22] the algorithm produces the inverse matrix (μ_{k}^{(i)}/μ) where μ_{k}^{(i)}, μ ∈ ZZ to n × n matrix (ν_{k}^{(i)}), which is invertible because of the construction of the vectors ν^{(i)}. Then p^{μY_{k}^{(j_{1})}} = p^{∑_{1≤i≤n} μ_{k}^{(i)}α_{π^{(i)}(j_{1})}^{(i)}} and the algorithm computes the right side of this equality. The algorithm also computes p^{μZ_{k}^{(j_{2})}}. Similar computations can be made for different primes p. The vectors Y^{(1)} = (Y_{1}^{(1)}, ⋯, Y_{n}^{(1)}), ⋯, Y^{(t_{1})} = (Y_{1}^{(t_{1})}, ⋯, Y_{n}^{(t_{1})}) and Z^{(1)} = (Z_{1}^{(1)}, ⋯, Z_{n}^{(1)}), ⋯, Z^{(t_{2})} = (Z_{1}^{(t_{2})}, ⋯, Z_{n}^{(t_{2})}) are considered as candidates for being exponents vectors in the numerator and denominator of a (t_{1}, t_{2})-sparse representation of f. The algorithm represents them by p^{μY_{k}^{(j_{1})}}, p^{μZ_{k}^{(j_{2})}}. The algorithm tests, whether Y^{(j)} ≠ Y^{(l)}, Z^{(j)} ≠ Z^{(l)} for j ≠ l.

The then algorithm tests whether these candidates fit. For this aim consider a linear system

∑_{1≤i≤t_{1}} ϕ_{i}p_{1}^{μY_{1}^{(i)}l} ⋯ p_{n}^{μY_{n}^{(i)}l} = ∑_{1≤i≤t_{2}} ψ_{i}p_{1}^{μZ_{1}^{(i)}l} ⋯ p_{n}^{μZ_{n}^{(i)}l}f(p_{1}^{μl}, ⋯, p_{n}^{μl}), 1 ≤ l ≤ 2(t_{1} + t_{2})^{2} (7)

in the unknown coefficients ϕ_{i}, ψ_{i} of the (t_{1}, t_{2})-sparse representation of f currently being tested. (In (7) we skip the equations for which f(p_{1}^{μl}, …, p_{n}^{μl}) = ∞). Lemma 1 implies that (7) is solvable if and only if exponent vectors Y^{(j)}, Z^{(j)} fit (we apply here lemma 1 probably not to rational functions, since the exponents Y_{k}^{(i)}, Z_{k}^{(i)} could be rational, but it is still valid by making a replacement of the variables X_{i} → \overline{X_{i}}^{μl}, 1 ≤ i ≤ n). If (7) is solvable then Y_{k}^{(i)}, Z_{k}^{(i)} are integers because of lemma 3a), moreover it has a unique solution by lemma 3b). This completes the description of the algorithm for f being minimally (t_{1}, t_{2})-sparse. To treat the case when we are only told that f is (t_{1}, t_{2})-sparse, we proceed as in Section 3.

Now we proceed to the complexity bounds. Let us assume we are given the black box for a (t_{1}, t_{2})-sparse rational function. The algorithm produces (t_{1} + t_{2})^{0((t_{1}+t_{2})n)} integer vectors ν^{(i)} and, for each of these, applies the algorithm from Section 3 to the univariate rational function fν_{(i)}. This part of the algorithm requires ((t_{1} + t_{2})^{(t_{1}+t_{2})n} log d)^{O(1)} arithmetic operations with depth ((t_{1}+t_{2})n log d)^{0(1)}. The algorithm then selects, for each i, 1 ≤ i ≤ n, some (t_{1}, t_{2})-sparse representation of fν_{(i)} and also two permutations π^{(i)}, σ^{(i)}. This is again within the same bounds. The algorithm then solves (t_{1}+t_{2})^{0((t_{1}+t_{2})n)} p-power forms of linear systems of type (5), (6). To invert n × n matrix (ν_{k}^{(i)}), n^{0(1)} arithmetic operations are used with depth log ^{0(1)}n. Since μ_{k}^{(i)}, μ ≤ (t_{1} + t_{2})^{O((t_{1}+t_{2})n^{2})} computation of p^{μ}, p^{μY_{k}^{(j_{1})}}, p^{μZ_{k}^{(j_{2})}} can be done within the same complexity bounds. The same applies to solving system (7). If we are only told that f is (t_{1}, t_{2})-sparse, the additional search required by the algorithm does not change the complexity.

We are also able to give some bounds on the degree d of a sparse representation. Assume that A is a bound for all the exponents α_{j}^{(i)}, β_{j}^{(i)} found for the univariate rational functions fν_{(i)} (such a bound can be found using the techniques of Section 3). We can then bound d by looking at p-power forms of the linear systems (5) and (6); in fact d ≤ A(t_{1}+t_{2})^{0((t_{1}+t_{2})n^{2})}. Thus, we can formulate the main result of the paper:

Theorem. 1)  One  can  construct  some  (t_{1}, t_{2})-sparse  repre-

sentation ∑_{1≤i≤t_{1}} a_{i}X_{1}^{j_{1}^{(i)}} ⋯ X_{n}^{j_{n}^{(i)}}/ ∑_{1≤i≤t_{2}} b_{i}X_{1}^{k_{1}^{(i)}} ⋯ X_{n}^{k_{n}^{(i)}} of (t_{1}, t_{2})-sparse rational function f

in ((t_{1} + t_{2})^{(t_{1}+t_{2})n} log d)^{O(1)} arithmetic operations with the depth ((t_{1} + t_{2})n log d)^{O(1)}.

2) the exponents j_{l}^{(i)}, k_{l}^{(i)} do not exceed d ≤ M(t_{1} + t_{2})^{O(t_{1}+t_{2})n^{2})} where M is the bound on bitsizes of all the outputs of applications of a black box during the computation.

Appendix. For the convenience of the reader, we give a short proof of the result about complex varieties that was needed in the proof of Lemma 11. This result is true for varieties over any algebraically closed field of characteristic 0, but the proof is more complex and depends on the Hilbert Irreducibility Theorem instead of elementary topological notions.

Lemma 12. Let 𝔚 be an irreducible constructible set in C^{n} (i.e. a constructible set whose Zariski closure is irreducible). Assume that for each ν = (ν_{1}, …, ν_{n}) ∈ 𝔚 there exist γ_{1}, …, γ_{n} ∈ ZZ, not all zero, such that ∑_{i=1}^{n} γ_{i}ν_{i} = 0. Then there exist γ̃_{1}, …, γ̃_{n} ∈ ZZ, not all zero, such that ∑_{i=1}^{n} γ̃_{i}ν_{i} = 0 for all (ν_{1}, …, ν_{n}) ∈ 𝔚.

Proof. If 𝔚 has dimension 0, then it is a point and we are done. Therefore assume dim 𝔚 > 0. By definition, 𝔚 is open in its Zariski closure \overline{𝔚}. Therefore there exists a point ν ∈ 𝔚 that is non-singular in \overline{𝔚}. We select a sufficiently small ϵ such that 𝔚_{ϵ} = 𝔚 ∩ {x | ∥x − ν∥ ≤ ϵ} will be closed in the usual topology and contain an open subset of 𝔚. For each (γ_{1}, …, γ_{n}) ∈ ZZ^{n}, not all γ_{i} zero, let H_{γ_{1},...,γ_{n}} = {(ν_{1}, …, ν_{n}) ∈ 𝔚| ∑_{i=1}^{n} γ_{i}ν_{i} = 0}. Since 𝔚_{ϵ} is closed, the Baire Category Theorem ([24], p. 139) implies that for some (γ̃_{1}, …, γ̃_{n}), H_{γ̃_{1},...,γ̃_{n}} contains an open subset of 𝔚_{ϵ} (and so, of 𝔚). Therefore dim(H_{γ̃_{1},...,γ̃_{n}} ∩ \overline{𝔚}) = dim \overline{𝔚}. Since \overline{𝔚} is irreducible, we must have (H_{γ̃_{1},...,γ̃_{n}} ∩ \overline{𝔚}) = \overline{𝔚} (c.f. [26], p. 54) so \overline{𝔚} ⊆ H_{γ̃_{1},...,γ̃_{n}}

Acknowledgement. We are indebted to Volker Strassen for motivating the problem and a number of simulating discussions.

References

[1] Ben-Or, M. and Tiwari, P.A., A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation, Proc. 20^{th} STOC ACM (1989), pp.301–309.

[2] Borodin, A. and Tiwari, P.A., On the Decidability of Sparse Univariate Polynomial Interpolation, Research Report RC 14923, IBM T. J. Watson Research Center, New York, 1989.

[3] Chistov, A.L., An Algorithm of Polynomial Complexity for Factoring Polynomials and Finding the Components of a Variety in Subexponential Time, J. Sov. Math., 34, No. 4 (1986).

[4] Chistov, A. L., Grigoriev, D. Yu., Complexity of quantifier elimination in the firstorder theory of algebraically closed fields, Lecture Notes Computer Science (1984), vol. 176, pp. 17–31.

[5] Evans, R.J. and Isaacs, I.M., Generalized Vandermonde Determinants and Roots of Unity of Prime Order, Proc. of the AMS (1976), 58.

[6] Fitchas, N., Galligo, A., Morgenstern, J., Sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields, Journal of Pure and Applied Algebra, (1990), 67, pp. 1–14.

[7] Grigoriev, D. Yu., Factoring Polynomials over a Finite Field and Solving Systems of Algebraic Equations, J. Sov. Math., 34, No. 4 (1986), pp. 1762–1803.

[8] Grigoriev, D. Yu., Complexity of deciding Tarski algebra, Journal of Symbolic Computation (1988), 5, pp. 65–108.

[9] Grigoriev, D.Yu., and Karpinski, M., The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC, Proc. 28^{th} IEEE FOCS (1987), pp. 166–172.

[10] Grigoriev, D.Yu., Karpinski, M., Singer, M., Interpolation of Sparse Rational Functions without Knowing Bounds on Exponents, Proc. 31^{st} IEEE FOCS (1990), pp. 840– 847.

[11] Grigoriev, D.Yu., Karpinski, M., Singer, M., Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields, SIAM J. Comp., 19, No. 6, (1990), pp. 1059–1063.

[12] Grigoriev, D. Yu., Karpinski, M., Singer, M., The interpolation problem for k-sparse sums of eigenfunctions of operators, Advances in Applied Mathematics, (1991), 12, pp. 76–81.

[13] Grigoriev, D.Yu., and Vorobjov, N.N., Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Computation (1988), 5, pp. 37–64.

[14] Heintz, J., Roy, M.-F., Solerno, P., Complexité du principe de Tarski-Seidenberg, C.R.A.S. Paris, t. 309, (1989), pp. 825–830.

[15] Kaltofen, E., Uniform Closure Properties of P -computable Functions, Proc. 18^{th} ACM STOC (1986), pp. 330–337.

[16] Kaltofen, E. and Trager, B., Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators, 29^{th} IEEE FOCS (1988), pp. 296–305.

[17] Kaltofen, E., Yagati, L., Improved Sparse Multivariate Polynomial Interpolation, Report 88-17, Dept. of Computer Science, Rensselaer Polytechnic Institute, (1988).

[18] Kaplanski, I., An Introduction to Differential Algebra, Hermann (1957), Paris.

[19] Karpinski, M., Boolean Circuit Complexity of Algebraic Interpolation Problems, Proc. CSL’88, Lecture Notes in Computer Science 385 (1989), Springer-Verlag, pp. 138-147.

[20] Karpinski, M., and Meyer auf der Heide, F., On the Complexity of Genuine Polynomial Computation, Proc 15^{th} MFCS (1990), LNCS 452, Springer-Verlag, pp. 362–368.

[21] Karpinski, M. and Werther, T., VC Dimension and Learnability of Sparse Polynomials and Rational Functions, University of Bonn (1989), Research Report No. 8537-CS.

[22] Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proc. 18 STOC, ACM (1986), pp. 338–339.

[23] Pan, V., Reif, J., Some polynomial and Toeplitz matrix computations, Proc. 28^{th} FOCS IEEE (1987), pp. 173–184.

[24] Royden, H.L., Real Analysis, Second Edition, MacMillan Company, New York, (1971).

[25] Strassen, V., Vermeidung von Divisionen, J. Reine und Angewandte Math. (1973), 65, pp. 182–202.

[26] Shafarevich, I., Basic Algebraic Geometry, Springer-Verlag, New York, (1977).

[27] Zippel, R.E., Probabilistic Algorithms for Sparse Polynomials, Lecture Notes in Computer Science 72, Springer-Verlag (1979), pp. 216–226.

[28] Zippel, R.E., Interpolating Polynomials from their Values, J. Symb. Comp., 9, (1990), pp. 375–403.