| A black box polynomial is an object that takes as input a value for each variable and evaluates the polynomial at the given input. The process of determining the coefficients and terms of a black box polynomial is the problem of black box polynomial interpolation. Two major approaches have been addressing such purpose: the dense algorithms whose computational complexities are sensitive to the degree of the target polynomial, and the sparse algorithms that take advantage of the situation when the number of non-zero terms in a designate basis is small. In this dissertation we cover power, Chebyshev, and Pochhammer term bases. However, a sparse algorithm is less efficient when the target polynomial is dense, and both approaches require as input an upper bound on either the degree or the number of non-zero terms. By introducing randomization into existing algorithms, we demonstrate and develop a probabilistic approach which we call “early termination.” In particular we prove that with high probability of correctness the early termination strategy makes different polynomial interpolation algorithms “smart” by adapting to the degree or to the number of non-zero terms during the process when either is not supplied as an input. Based on the early termination strategy, we describe new efficient univariate algorithms that race a dense against a sparse interpolation algorithm in order to exploit the superiority of one of them. We apply these racing algorithms as the univariate interpolation procedure needed in Zippel's multivariate sparse interpolation method. We enhance the early termination approach with thresholds, and present insights to other such heuristic improvements. Some potential of the early termination strategy is observed for computing a sparse shift, where a polynomial becomes sparse through shifting the variables by a constant. |
