Malod and the Pascaline

摘要

We make explicit the central role played by the binomial coefficients in the description of the coefficient-function of a polynomial computed in polynomial time (no bound on the degree), following the works of Guillaume Malod. Our results are obtained with the help of a universal polynomial which is simpler than the one used by Malod. As a corollary, with the help of a result of Peter Buergisser, we establish in characteristic zero a connection between Leslie Valiant's question VNP =?VP (bounded degree) and its unbounded degree version, generalizing what Malod had previously done in finite characteristic.