Depth-first search for tensor rank and border rank over finite fields

Abstract

We present an $O^{\ast }\left(|\mathbb{F}{|}^{(R-n_{\ast })\left({\sum }_d{n}_d\right)+n_{\ast }}\right)$-time algorithm for determining whether a tensor of shape $n_0\times \cdots \times n_{D-1}$ over a finite field $\mathbb{F}$ has rank $\le R$, where $n_{\ast }:={\max }_d{n}_d$; we assume without loss of generality that $\forall d:n_d\le R$. We also extend this problem to its border rank analog, i.e., determining tensor rank over rings of the form $\mathbb{F}[x]/(x^H)$, and give an $O^{\ast }\left(|\mathbb{F}{|}^{H{\sum }_{1\le r\le R}{\sum }_d\min (r,n_d)}\right)$-time algorithm. Both of our algorithms use polynomial space.

arXiv comment10 pages, to appear in MURJ Fall 2024