Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Certain questions concerning the arithmetic complexity of univariate polynomial evaluation are considered. The principal technical results show that there exist polynomials f,g, and h with h = fg, such that h requires substantially 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. The question of the relative complexities of f and fg is viewed as a special case of the following question: given an operator Δ which maps polynomials to sets of polynomials, what savings in arithmetic operations is achievable by evaluating some polynomial h ε{lunate} Δ(f) rather than f? Observations and open questions concerning several operators are discussed. © 1978.
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
T. Graham, A. Afzali, et al.
Microlithography 2000