Séminaire Calcul Formel

Derandomization and Absolute Reconstruction for Sums of Powers of Linear Forms

by Dr Mateusz Skomra (LAAS, CNRS)




We study the decomposition of multivariate polynomials as sums
of powers of linear forms. In this talk, we focus on the following
problem: given a homogeneous polynomial of degree 3 over a field, decide
whether it can be written as a sum of cubes of linearly independent
linear forms over an extension field. This task can be equivalently
expressed as a decomposition problem for symmetric tensors of order 3.
Even if the input polynomial has rational coefficients, the answer may
depend on the choice of the extension field. We study the cases where
the extension field is either the real or the complex numbers. Our main
result is an algorithm that solves this problem in polynomial time when
implemented in the bit model of computation. Furthermore, contrary to
the previous algorithms for the same problem, our algorithm is algebraic
and does not make any appeal to polynomial factorization. We also
discuss how our algorithm can be extended to other tensor decomposition
problems. This talk is based on a joint work with Pascal Koiran.