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

We present an $O^{\ast }\left(\mathrm{\mid }\mathbb{F}{\mathrm{\mid }}^{(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 $\mathrm{\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]\mathrm{/}(x^H)$, and give an $O^{\ast }\left(\mathrm{\mid }\mathbb{F}{\mathrm{\mid }}^{H{\sum }_{1\le r\le R}{\sum }_d\min (r,n_d)}\right)$-time algorithm. Both of our algorithms use polynomial space.