Interpolation in Valiant's theory

Pascal Koiran, Sylvain Perifel

We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit…