- M. Shamos. 1977. Recent technical reports. Abstract: Certain questions concerning the arithmetic complexity of unlvarlate polynomial evaluation are considered. Given an operator which maps polynomials to sets of polynomials, the objective is to investigate the relative savings in arithmetic operations achievable by evaluating some polynomlai h(x) ~ g(f(x)) rather than f(x). The main technical results concern the operator that maps f to the set of nontrlvlal polynomial multiples of f. It is shown that there exist polynomials f, g, and h, with h fg, such that h requires substantlally fewer arithmetic operations than either f or g. However, if the coefficients of f are algebraically independent, then any h fg Is as hard to evaluate as f. Several observations and open questions concerning other operators are discussed.
