arXiv:2604.00591 · v2

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields

首次提交 2026-04-01 15:58

版本更新 2026-11-03 11:51

雷达观测 2026-11-04 23:40

摘要

In Grochow and Qiao (\emph{SIAM J. Comput.}, 2023), the complexity class Tensor Isomorphism (TI) was introduced and isomorphism problems for groups, algebras, and polynomials were shown to be TI-complete. In this paper, we study average-case algorithms for several TI-complete problems over finite fields, including algebra isomorphism, matrix code conjugacy, and $4$-tensor isomorphism. Our main results reveal a rich landscape of average-case complexities of Tensor Isomorphism problems, despite their equivalence in the worst-case setting. Over the finite field of order $q$, we devise (1) average-case \emph{polynomial-time} algorithms for algebra isomorphism and matrix code conjugacy that succeed for $1/Θ(q)$ fraction of inputs; (2) an average-case \emph{polynomial-time} algorithm for the $4$-tensor isomorphism that succeeds for $1/q^{Θ(1)}$ fraction of inputs; and (3) an average-case \emph{polynomial-time} algorithm for the orthogonal $3$-tensor isomorphism that succeed for $1-1/\poly(n)$ fraction of $n\times n\times n$ tensors. Our main technical contribution is to introduce the spectral properties of random matrices into algorithms for TI-complete problems. This leads to not only new algorithms but also new questions in random matrix theory over finite fields. To settle these questions, we need to extend both the generating function approach as in Neumann and Praeger (\emph{J. London Math. Soc.}, 1998) and the character sum method of Gorodetsky and Rodgers (\emph{Trans. Amer. Math. Soc.}, 2021).

作者备注：60 pages, add average-case polynomial-time algorithm for orthogonal tensor isomorphism over finite field