Equivalence test for the trace iterated matrix multiplication polynomial

Abstract

An m-variate polynomial f is affine equivalent to an n-variate polynomial g if m > n and there is a full rank n * m matrix A and a n-dimensional vector b such that f(x) = g(Ax + b). Given blackbox access to f and g (i.e membership query access) the affine equivalence test problem is to determine whether f is affine equivalent to g, and if yes then output a rank n matrix A and a vector b such that f(x) = g(Ax + b). This problem is at least as hard as graph isomorphism and algebra isomorphism even when the coefficients of f and g are given explicitly (Agarwal and Saxena, STACS 2006), and has been studied in literature by fixing g to be some interesting family of polynomials. In this work, we fix g to be the trace of the product of d, w * w symbolic matrices. We call this polynomial 'Trace Iterated Matrix Multiplication' polynomial (Tr-IMM). Kayal, Nair, Saha and Tavenas (CCC 2017) gave an efficient (i.e polynomial in m,w,d) randomized algorithm for the affine equivalence test of the 'Iterated Matrix Multiplication' polynomial (IMM), which is the (1,1)-th entry of the product of these symbolic matrices. Although the definitions of IMM and Tr-IMM are closely related and their circuit complexities are very similar, it is not clear whether an efficient affine equivalence test algorithm for IMM implies the same for Tr-IMM. In this thesis, we take a step towards showing that equivalence test for IMM and Tr-IMM have different complexity. We show that equivalence test for Tr-IMM reduces in randomized polynomial time to equivalence test for the determinant polynomial (Det), under mild conditions on the underlying field. If the converse is also true then equivalence tests for Tr-IMM and Det are randomized polynomial time equivalent. It would then follow from the work of Gupta, Garg, Kayal and Saha (ICALP 2019) that equivalence test for Tr-IMM over rationals is at least as hard as Integer Factoring. This would then be in sharp contrast with the complexity of equivalence test for Tr-IMM over rationals which can be solved efficiently in randomized polynomial time (by Kayal, Nair, Saha and Tavenas (CCC 2017)).

Recent Update: Soon after the thesis is written, we (together with Vineet Nair) have succeeded in showing the converse direction. So, the above conclusion is indeed true! This work has been accepted at the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).