{"id":"arxiv/2604.00591","url":"https://arxiv.org/abs/2604.00591","tags":["cs.CC","cs.DS","math.PR"],"score":0,"title":"On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields","domain":"cs.CC","source":"arxiv","authors":["Tiange Li","Yinan Li","Youming Qiao","Dacheng Tao","Yingjie Wang"],"reviews":0,"subject":"cs.CC","summary":"In Grochow and Qiao (SIAM J. Comput., 2021), 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 are as follows. Over the finite field of order $q$, we devise (1) average-case polynomial-time algorithms for algebra isomorphism and matrix code conjugacy that succeed in a $1/Θ(q)$ fraction of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}