Polynomials with 0-1 Coefficients That are Hard to Evaluate
Richard J. Lipton · SIAM Journal on Computing · 1978
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.