Faster search for tensor decomposition over finite fields

We present an $O^{\ast }(\mathrm{\mid }\mathbb{F}{\mathrm{\mid }}^{\min \{R,{\sum }_{d\ge 2}{n}_d\}+(R-n_0)({\sum }_{d\mathrm{\ne }0}{n}_d)})$-time algorithm for determining whether the rank of a concise tensor $T\in {\mathbb{F}}^{n_0\times \cdots \times n_{D-1}}$ is $\le R$, assuming $n_0\ge \cdots \ge n_{D-1}$ and $R\ge n_0$. For 3-dimensional tensors, we have a second algorithm running in $O^{\ast }(\mathrm{\mid }\mathbb{F}{\mathrm{\mid }}^{n_0+n_2+(R-n_0+1-r_{\ast })(n_1+n_2)+r_{\ast }^2})$ time, where $r_{\ast }:=\lfloor \frac{R}{n_0}\rfloor +1$. Both algorithms use polynomial space and improve on our previous work, which achieved running time $O^{\ast }(\mathrm{\mid }\mathbb{F}{\mathrm{\mid }}^{n_0+(R-n_0)({\sum }_d{n}_d)})$.