Murthy, Janaky ;
Nair, Vineet ;
Saha, Chandan
Randomized PolynomialTime Equivalence Between Determinant and TraceIMM Equivalence Tests
Abstract
Equivalence testing for a polynomial family {g_m}_{m β β} over a field π½ is the following problem: Given blackbox access to an nvariate polynomial f({π±}), where n is the number of variables in g_m for some m β β, check if there exists an A β GL(n,π½) such that f({π±}) = g_m(A{π±}). 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: IMM_{w,d} (the (1,1) entry of the product of d many wΓ w symbolic matrices) and TrIMM_{w,d} (the trace of the product of d many wΓ w symbolic matrices). The families  Det, IMM and TrIMM  are VBPcomplete under pprojections, 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 TrIMM (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 β: a randomized polytime equivalence testing for IMM over β is known [Neeraj Kayal et al., 2019], whereas [Ankit Garg et al., 2019] showed that equivalence testing for Det over β is integer factoring hard (under randomized reductions and assuming GRH). To our knowledge, the complexity of equivalence testing for TrIMM was not known before this work. We show that, despite the syntactic similarity between IMM and TrIMM, equivalence testing for TrIMM and that for Det are randomized polytime 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 wellstudied problem in computer algebra, namely the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following:
1) Testing equivalence of polynomials to TrIMM_{w,d}, for d β₯ 3 and w β₯ 2, is randomized polynomialtime Turing reducible to testing equivalence of polynomials to Det_w, the determinant of the w Γ w matrix of formal variables. (Here, d need not be a constant.)
2) FMAI is randomized polynomialtime Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {TrIMM_{w,3}}_{w β β}. These results, in conjunction with the randomized polytime reduction (shown in [Ankit Garg et al., 2019]) from determinant equivalence testing to FMAI, imply that the four problems  FMAI, equivalence testing for TrIMM and for Det, and the 3tensor isomorphism problem for the family of matrix multiplication tensors  are randomized polytime equivalent under Turing reductions.
BibTeX  Entry
@InProceedings{murthy_et_al:LIPIcs:2020:12741,
author = {Janaky Murthy and Vineet Nair and Chandan Saha},
title = {{Randomized PolynomialTime Equivalence Between Determinant and TraceIMM Equivalence Tests}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {72:172:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ΔΎ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12741},
URN = {urn:nbn:de:0030drops127419},
doi = {10.4230/LIPIcs.MFCS.2020.72},
annote = {Keywords: equivalence testing, determinant, trace of the matrix product, fullmatrix algebra isomorphism}
}
18.08.2020
Keywords: 

equivalence testing, determinant, trace of the matrix product, fullmatrix algebra isomorphism 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 