License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.72
URN: urn:nbn:de:0030-drops-127419
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12741/
Murthy, Janaky ;
Nair, Vineet ;
Saha, Chandan
Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests
Abstract
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 ℚ: a randomized poly-time 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 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.
BibTeX - Entry
@InProceedings{murthy_et_al:LIPIcs:2020:12741,
author = {Janaky Murthy and Vineet Nair and Chandan Saha},
title = {{Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {72:1--72:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12741},
URN = {urn:nbn:de:0030-drops-127419},
doi = {10.4230/LIPIcs.MFCS.2020.72},
annote = {Keywords: equivalence testing, determinant, trace of the matrix product, full-matrix algebra isomorphism}
}
|
Keywords: |
|
equivalence testing, determinant, trace of the matrix product, full-matrix algebra isomorphism |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
