Séminaire Calcul Formel
# Derandomization and Absolute Reconstruction for Sums of Powers of Linear Forms

→
Europe/Paris

https://bbb.unilim.fr/b/vac-m6r-7dv
#### https://bbb.unilim.fr/b/vac-m6r-7dv

Description

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.