Jakob Bæk Tejs Knudsen

Fast Evaluation of Polynomials with Rational Preprocessing

It is proved that an $n$-multiplication chain cannot parametrize all value vectors at $2n$ distinct evaluation points, even with arbitrary preprocessing, and strengthens the lower bound of Pan (STOC 1978), who proved a tight bound for general, complex preprocessing.