Title: Bilinear Complexity of 3-tensor Linked to Coding Theory
Abstract: A central problem in algebraic complexity theory is
the determination of the complexity, with respect to the
noncommutative model of computation, of problems that can
be modelled by bilinear forms. The bilinear complexity of an
algorithm is defined as the minimum number of non-scalar
multiplications required to execute it. Each bilinear map is
a 3-tensor, and its bilinear complexity is called its tensor rank,
which is the minimum number of rank-one matrices whose span
contains its first slice space. In 1989, H\aastad proved that
computing the tensor rank of a 3-tensor is NP-complete over any
finite field and over the rationals is NP-hard. In this talk, we present
upper bounds on the tensor rank of certain classes of 3-tensors and
give explicit constructions of spaces spanned by rank-one matrices
containing their first slice spaces. We then show how these results
can be applied in coding theory to derive upper bounds on the
complexity of a generator tensor of some rank-metric codes. In particular,
we compute the tensor rank of a family of $\mathbb{F}_q^m$-linear
codes and show that its members are extremal with respect to Kruskal’s
tensor rank bound.