2024/01/12 by Yang, Jason
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2401.06857
We show that finding rank-R decompositions of a 3D tensor, for R≤ 4, over a fixed finite field can be done in polynomial time. However, if some cells in the tensor are allowed to have arbitrary values, then rank-2 is NP-hard over the integers modulo 2. We also explore rank-1 decomposition of a 3D tensor and of a matrix where some cells are allowed to have arbitrary values.