05.12.2008

We construct a deterministic polynomial time (deterministic boolean NC [C 85]) algorithm for interpolating arbitrary t-sparse rational functions. It is the first deterministic polynomial time algorithm for this problem. Given an arbitrary rational function f (in the most general setting given by a black box), such that f = P/Q, P,Q ∈ Z[x₁, ..., x_n] for P. Q t-sparse, relatively prime, with coefficients bounded in absolute value by 2ⁿ, and such that deg_xi(P), deg_xi(Q) < d, the algorithm works in O(log³(ndt)) boolean parallel time and O(n⁴d^7.5t^17.5log n log d log t) boolean processors. (In general, if the coefficients of P and Q are bounded in the absolute value by the function S. S: N → N, S(n) ≥ n, there exists an implementation (cf. [BCP 83]) of our algorithm in NC³(log S).)

Having established the above deterministic circuit complexity upper bounds for the Rational Function Interpolation, the very challenging practical matter arises to improve on the number of boolean processors (or the sequential deterministic time) of our algorithm.