  We study the decomposition of multivariate polynomials as sums of powers of
linear forms.
  As one of our main results we give an algorithm for the following problem:
given a homogeneous polynomial of degree 3, decide whether it can be written as
a sum of cubes of linearly independent linear forms with complex coefficients.
Compared to previous algorithms for the same problem, the two main novel
features of this algorithm are:
  (i) It is an algebraic algorithm, i.e., it performs only arithmetic
operations and equality tests on the coefficients of the input polynomial. In
particular, it does not make any appeal to polynomial factorization.
  (ii) For an input polynomial with rational coefficients, the algorithm runs
in polynomial time when implemented in the bit model of computation.
  The algorithm relies on methods from linear and multilinear algebra
(symmetric tensor decomposition by simultaneous diagonalization).
  We also give a version of our algorithm for decomposition over the field of
real numbers. In this case, the algorithm performs arithmetic operations and
comparisons on the input coefficients.
  Finally we give several related derandomization results on black box
polynomial identity testing, the minimization of the number of variables in a
polynomial, the computation of Lie algebras and factorization into products of
linear forms.
