Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests.

Equivalence testing for a polynomial family gmm�N over a field F is the following problem: Given black-box access to an n-variate polynomial f(x), where n is the number of variables in gm for some m � N, check if there exists an A � GL(n, F) such that f(x) = gm(Ax). If yes, then output such an A. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the family of iterated matrix multiplication polynomials. Two popular variants of the iterated matrix multiplication polynomial are: IMMw,d (the (1, 1) entry of the product of d many w A� w symbolic matrices) and Tr-IMMw,d (the trace of the product of d many w A� w symbolic matrices). The families - Det, IMM and Tr-IMM - are VBP-complete under p-projections, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is �yes� for Det and Tr-IMM (modulo the use of randomness). The above result may appear a bit surprising as the complexity of equivalence testing for IMM and that for Det are quite different over Q: a randomized poly-time equivalence testing for IMM over Q is known 28, whereas 15 showed that equivalence testing for Det over Q is integer factoring hard (under randomized reductions and assuming GRH). To our knowledge, the complexity of equivalence testing for Tr-IMM was not known before this work. We show that, despite the syntactic similarity between IMM and Tr-IMM, equivalence testing for Tr-IMM and that for Det are randomized poly-time Turing reducible to each other over any field of characteristic zero or sufficiently large. The result is obtained by connecting the two problems via another well-studied problem in computer algebra, namely the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following: 1. Testing equivalence of polynomials to Tr-IMMw,d, for d � 3 and w � 2, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Detw, the determinant of the w A� w matrix of formal variables. (Here, d need not be a constant.) 2. FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMMw,3}w�N. These results, in conjunction with the randomized poly-time reduction (shown in 15) from determinant equivalence testing to FMAI, imply that the four problems - FMAI, equivalence testing for Tr-IMM and for Det, and the 3-tensor isomorphism problem for the family of matrix multiplication tensors - are randomized poly-time equivalent under Turing reductions. © Nathalie Bertrand; licensed under Creative Commons License CC-BY 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).