Search Results

Documents authored by Murthy, Janaky


Document
Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests

Authors: Janaky Murthy, Vineet Nair, and Chandan Saha

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


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.

Cite as

Janaky Murthy, Vineet Nair, and Chandan Saha. Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{murthy_et_al:LIPIcs.MFCS.2020.72,
  author =	{Murthy, Janaky and Nair, Vineet and Saha, Chandan},
  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 =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.72},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail