文章基本信息

标题：Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests
本地全文：下载
作者：Janaky Murthy ; Vineet Nair ; Chandan Saha 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：72:1-72:16
DOI：10.4230/LIPIcs.MFCS.2020.72
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Equivalence testing for a polynomial family {g_m}_{m â^^ â".} over a field ð"½ is the following problem: Given black-box access to an n-variate 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 Tr-IMM_{w,d} (the trace of the product of d many wÃ- 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 â"S: a randomized poly-time equivalence testing for IMM over â"S is known [Neeraj Kayal et al., 2019], whereas [Ankit Garg et al., 2019] showed that equivalence testing for Det over â"S 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-IMM_{w,d}, for d â¥ 3 and w â¥ 2, is randomized polynomial-time 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 polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMM_{w,3}}_{w â^^ â".}. These results, in conjunction with the randomized poly-time reduction (shown in [Ankit Garg et al., 2019]) 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.
关键词：equivalence testing; determinant; trace of the matrix product; full-matrix algebra isomorphism