  De-bordering is the task of proving that a border complexity measure is
bounded from below, by a non-border complexity measure. This task is at the
heart of understanding the difference between Valiant's determinant vs
permanent conjecture, and Mulmuley and Sohoni's Geometric Complexity Theory
(GCT) approach to settle the P \neq NP conjecture. Currently, very few
de-bordering results are known.
  In this work, we study the question of de-bordering the border Waring rank of
polynomials. Waring and border Waring rank are very well studied measures, in
the context of invariant theory, algebraic geometry and matrix multiplication
algorithms. For the first time, we obtain a Waring rank upper bound that is
exponential in the border Waring rank and only *linear* in the degree. All
previous results were known to be exponential in the degree.
  According to Kumar's recent surprising result (ToCT'20), a small border
Waring rank implies that the polynomial can be approximated as a sum of a
constant and a small product of linear polynomials. We prove the converse of
Kumar's result, and in this way we de-border Kumar's complexity, and obtain a
new formulation of border Waring rank, up to a factor of the degree. We phrase
this new formulation as the orbit closure problem of the product-plus-power
polynomial, and we successfully de-border this orbit closure. We fully
implement the GCT approach against the power sum, and we generalize the ideas
of Ikenmeyer-Kandasamy (STOC'20) to this new orbit closure. In this way, we
obtain new multiplicity obstructions that are constructed from just the
symmetries of the points and representation theoretic branching rules, rather
than explicit multilinear computations.
  Furthermore, we realize that the generalization of our converse of Kumar's
theorem to square matrices gives a homogeneous formulation of Ben-Or and Cleve
(SICOMP'92). This results ...
