Fixed-parameter tractability of canonical polyadic decomposition over finite fields

2024/05/19 by Jason Yang, Yang, Jason
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2405.11699

openalex publication_date 2024/05/19 · openalex created_date 2024/05/22 · openalex updated_date 2026/07/28

Abstract

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

Related

• New results in canonical polyadic decomposition over finite fields
• Low-Rank Tensor Decomposition over Finite Fields
• Canonical polyadic decomposition of third-order tensors: relaxed\n uniqueness conditions and algebraic algorithm
• Tight Lower Bound on the Tensor Rank based on the Maximally Square Unfolding
• Fundamental Conditions for Low-CP-Rank Tensor Completion