Information Technology Reference
In-Depth Information
Chapter 8
Malod and the Pascaline
Bruno Poizat
Presented to Somenath Biswas on
the occasion of his 60th birthday
Abstract
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 Bürgisser, 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.
=
·
·
Keywords
Complexity
Polynomials
Summations
8.1 Polynomials, Functions and Arithmetic Circuits
We compute polynomials, in several variables, with integer coefficients. For that, we
consider
arithmetic circuits
, with input gates labeled either by a variable or by the
constant
−
1; the other gates are binary (they receive two arrows) and perform either
GuillaumeMalod defended his doctorate in 2003 in Lyon; he visited Kanpur as a participant to a
cooperation program between IITK and Claude Bernard University. Blaise Pascal (1623-1662),
philosopher, mathematician and physicist; he discovered the recurrence relation between the
binomial coefficients (“Triangle de Pascal”), and invented the Pascaline, a mechanical device
performing arithmetic operations.
