Polynomials with 0-1 coefficients that are hard to evaluate

1 October 1975

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 6-10
https://doi.org/10.1109/sfcs.1975.25

Abstract

We show the existence of polynomials with 0-1 coefficients that are hard to evaluate even when arbitrary preconditioning is allowed. Further we show that there are power series with 0-1 coefficients such that their initial segments are hard to evaluate.

Keywords

This publication has 4 references indexed in Scilit:

Complexity measures and hierarchies for the evaluation of integers, polynomials, and n-linear forms
Published by Association for Computing Machinery (ACM) ,1975
Polynomials with Rational Coefficients Which are Hard to Compute
SIAM Journal on Computing, 1974
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
SIAM Journal on Computing, 1973
On the number of multiplications necessary to compute certain functions
Communications on Pure and Applied Mathematics, 1970

Cited by 7 articles