Polynomial-Time Power-Sum Decomposition of Polynomials

Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1

We give efficient algorithms for finding power-sum decomposition of an input polynomial $P(x)={\sum }_{i\le m}{p}_i(x{)}^d$ with component $p_i$s. The case of linear $p_i$s is equivale…