Fixed-parameter tractability of canonical polyadic decomposition over finite fields

Abstract

We present a simple proof that finding a rank-$R$ canonical polyadic decomposition of a 3-dimensional tensor over a finite field $\mathbb{F}$ is fixed-parameter tractable with respect to $R$ and $\mathbb{F}$. We also show a nontrivial upper bound on the time complexity of this problem.

12 pages; some proofs copied from arXiv:2401.06857; slightly refined result