The paper by Pascal Koiran and Subhayan Saha focuses on the decomposition of polynomials into sums of powers of linear forms.
The authors present a randomized algorithm to address whether a given homogeneous polynomial \( f \in K[x_1, ..., x_n] \) of degree \( d \) can be expressed as a linear combination of \( d \)-th powers of linearly independent complex linear forms.
From a theoretical point of view, algorithms addressing this problem already existed. The significance of the present paper lies in the effectiveness and low complexity of the proposed algorithm. As a randomized algorithm, the output will be approximate.
The primary contributions and findings of the study are summarized as follows:
The algorithm enhances the running time for degree 3 polynomials by a factor of \( n \) compared to the previous algorithm by P. Koiran and M. Skomra [Theor. Comput. Sci. 887, 63–84 (2021; Zbl 1483.13044)]. This optimization introduces a two-sided error to the algorithm.
The paper introduces a randomized blackbox algorithm for polynomials of degree greater than 3, which operates in polynomial time with respect to \( n \) and \( d \) in an algebraic model that allows only arithmetic operations and equality tests. This is different from a prior approach by N. Kayal [SODA 2011, 1409–1421 (2011; Zbl 1376.68166)], which relied on polynomial factorization and was not polynomial time in standard computational models.
If \( f \) has rational coefficients (i.e., \( K = \mathbb{Q} \)), the algorithm’s running time is polynomial in \( n \), \( d \), and the maximum bit size of any coefficient. This marks the first polynomial time algorithm for this problem over \( \mathbb{C} \) in the bit model of computation.
One of the limitations of this algorithm is that it requires the output decomposition points of the polynomial to be linearly independent. This represents the “simpler” case, even for the symbolic algorithms.