Title: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
Abstract: The authors consider the problem of reconstructing (i.e., interpolating) a t-sparse multivariate polynomial given a black box which will produce the value of the polynomial for any value of the arguments. It is shown that, if the polynomial has coefficients in a finite field $GF[q]$ and the black box can evaluate the polynomial in the field $GF[q^{\ulcorner 2\log_{q}(nt)+3 \urcorner}]$, where n is the number of variables, then there is an algorithm to interpolate the polynomial in $O(\log^3 (nt))$ boolean parallel time and $O(n^2 t^6 \log^2 nt)$ processors. This algorithm yields the first efficient deterministic polynomial time algorithm (and moreover boolean $NC$-algorithm) for interpolating t-sparse polynomials over finite fields and should be contrasted with the fact that efficient interpolation using a black box that only evaluates the polynomial at points in $GF[q]$ is not possible (cf. [M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski, Theoret. Comput. Sci., 1990, to appear]). This algorithm, together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf. [D. Yu. Grigoriev and M. Karpinski, in Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 166–172], [M. Ben-Or and P. Tiwari, in Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988, pp. 301–309]), yields for the first time the general deterministic sparse conversion algorithm working over arbitrary fields. (The reason for this is that every field of positive characteristic contains a primitive subfield of this characteristic, and so this method can be applied to the slight extension of this subfield.) The method of solution involves the polynomial enumeration techniques of [D. Yu. Grigoriev and M. Karpinski, op. cit.] combined with introducing a new general method of solving the problem of determining if a t-sparse polynomial is identical to zero by evaluating it in a slight extension of the coefficient field (i.e., an extension whose degree over this field is logarithmic in nt).