Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

Mrinal Kumar, Shubhangi Saraf

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T…