Polynomials with 0-1 coefficients that are hard to evaluate

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.