Abstract
The Waring rank of a homogeneous degree-d polynomial f is the least s, such that f can be written as s-many sum of d-th powers of linear forms. Computing Waring rank is closely related to tensor rank computation and optimal tensor decomposition. Interestingly, the Waring rank decomposition/reconstruction problem is intimately related to polynomial factoring in the restricted form [Kay'11]. We will review some of the recent developments in the related reconstruction/factoring regime, in algebraic complexity.
A very close, yet not-very-well-understood measure is the border Waring rank, where one involves the notion of algebraic approximation. The border complexity of polynomials plays an integral role in GCT (Geometric complexity theory) to approach P != NP. In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials, which has a small border-Σ^[2]ΠΣ circuit (or binomial complexity). In this talk, we will discuss the *converse* of Kumar’s result, which ramifies in a surprising new formulation of Waring rank and border Waring rank. We will also talk about some newly discovered connections between Waring rank and border Waring rank.