Algebraic Complexity Seminar

Sums of Powers of Linear Forms: Lower Bounds and Identity Testing

We will discuss a very simple model of algebraic computation: sums of powers of linear forms.  Lower bounds for this model (the number of powers of linear forms) are also known under the name of the Waring problem for polynomials.  We will give the "computer science" viewpoint on these lower bounds by proving the lower bounds via the "partial derivative method".

We will then discuss the polynomial identity testing problem for this model: given a sum of powers of linear forms, efficiently and deterministically decide whether the expression is zero.  I will discuss how there is such an algorithm for this problem, and discuss how there are still algorithmic challenges for this model (specifically, constructing small hitting sets).