The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles. The actual identity is much more general, and in particular, applies to any linear form raised to an arbitrary power. Saxena (2008) famously used this duality to derive identity testing algorithms for polynomials that are poly(n,d)-sums of powers of linear forms. This model (AKA sum-power-sum) coincides with the well-studied notion of Waring rank in mathematics.
In this talk, we will see two proofs of the duality trick due to Saxena and Shpilka respectively. Both these proofs use fairly elementary ideas about polynomials. We shall then see a different proof of correctness of Saxena's construction that uses mildly non-elementary algebraic geometry.
