10.12.2008

This paper gives a survey of some recent results on the parallel complexity of the sparse black box interpolation problem for multivariate polynomials and rational functions over arbitrary fields. In this setting, rather than the degree of the polynomial, the number of terms is of importance. Given a multivariate polynomial (or rational function) over an arbitrary field, as a black box (input oracle), and an information about its sparsity (a bound on the number of non-zero coefficients) we have to determine the complexity of reconstructing the polynomial. Some of the recent NC-algorithms and implementations using the computer-algebra system Scratchpad II are presented.

This paper is a revised version of a thesis for a Master's Degree in Computer Science, University of Bonn, August 1988.