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

Authors Janaky Murthy, Vineet Nair, Chandan Saha



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.72.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Author Details

Janaky Murthy
  • Indian Institute of Science, Bangalore, India
Vineet Nair
  • Technion Israel Institute of Technology, Haifa, Israel
Chandan Saha
  • Indian Institute of Science, Bangalore, India

Acknowledgements

We are thankful to Avi Wigderson for his suggestion on designing an equivalence testing algorithm for Tr-IMM at the end of VN’s presentation at CCC 2017. We would like to thank Christian Ikenmeyer for his question on equivalence testing for Tr-IMM which encouraged us to work on this problem. Thanks also to Neeraj Kayal and Ankit Garg for helpful discussions, and particularly to Neeraj for pointing us to [Joshua A. Grochow and Youming Qiao, 2019]. We thank the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.MFCS.2020.72

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • equivalence testing
  • determinant
  • trace of the matrix product
  • full-matrix algebra isomorphism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Manindra Agrawal and Nitin Saxena. Automorphisms of finite rings and applications to complexity of problems. In 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005, pages 1-17, 2005. Google Scholar
  2. Manindra Agrawal and Nitin Saxena. Equivalence of f-algebras and cubic forms. In 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006, pages 115-126, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  3. Manuel Araújo. Classification of Quadratic Forms. https://www.math.tecnico.ulisboa.pt/~ggranja/manuel.pdf, 2011.
  4. László Babai and Lajos Rónyai. Computing irreducible representations of finite groups. Mathematics of Computation, 55(192):705-722, 1990. Google Scholar
  5. Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic branching programs, border complexity, and tangent spaces. Electronic Colloquium on Computational Complexity (ECCC), 27:31, 2020. URL: https://eccc.weizmann.ac.il/report/2020/031.
  6. Peter A Brooksbank and James B Wilson. The module isomorphism problem reconsidered. Journal of Algebra, 421:541–559, 2015. Google Scholar
  7. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 386-395. IEEE Computer Society, 2016. Google Scholar
  8. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1-138, 2011. Google Scholar
  9. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications. SIAM J. Comput., 48(1):70-92, 2019. Google Scholar
  10. J. E. Cremona, T. A. Fisher, C. O'Neil, D. Simon, and M. Stoll. Explicit n-descent on elliptic curves III. algorithms. Math. Comput., 84(292):895-922, 2015. Google Scholar
  11. W. M. Eberly. Computations for algebras and group representations. PhD thesis, Department of Computer Science, University of Toronto, 1989. Google Scholar
  12. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput., 44(5):1173-1201, 2015. Google Scholar
  13. Georg Frobenius. Ueber die Darstellung der endlichen Gruppen durch lineare Substitutionen. Sitzungber. der Berliner Akademie, 7:994–1015, 1897. Google Scholar
  14. Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk. Wildness for tensors. Linear Algebra and its Applications, 566:212–244, 2019. Google Scholar
  15. Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant equivalence test over finite fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, pages 62:1-62:15, 2019. Google Scholar
  16. Fulvio Gesmundo. Geometric aspects of iterated matrix multiplication. Journal of Algebra, 461:42-64, 2016. Google Scholar
  17. Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova. Geometric complexity theory and matrix powering. Differential Geometry and its Applications, 55:106-127, 2017. Google Scholar
  18. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 59-68. ACM, 1986. Google Scholar
  19. Joshua A. Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, The University of Chicago, 2012. Available from URL: https://www.cs.colorado.edu/~jgrochow/grochow-thesis.pdf.
  20. Joshua A. Grochow and Youming Qiao. Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. CoRR, abs/1907.00309, 2019. Google Scholar
  21. Christian Ikenmeyer and Greta Panova. Rectangular kronecker coefficients and plethysms in geometric complexity theory. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 396-405. IEEE Computer Society, 2016. Google Scholar
  22. Gábor Ivanyos, Lajos Rónyai, and Joseph Schicho. Splitting full matrix algebras over algebraic number fields. Jounral of Algebra, 354:211-223, 2012. Google Scholar
  23. Erich Kaltofen and Barry M. Trager. Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. J. Symb. Comput., 9(3):301-320, 1990. Google Scholar
  24. Neeraj Kayal. Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of the 22nd Symposium on Discrete Algorithms, SODA 2011, pages 1409-1421, 2011. Google Scholar
  25. Neeraj Kayal. Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pages 643-662, 2012. Full text available from URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Projection.pdf.
  26. Neeraj Kayal, Vineet Nair, and Chandan Saha. Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Computational Complexity, 28(4):749-828, 2019. Google Scholar
  27. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth-three circuits. ACM Trans. Comput. Theory, 12(1), 2020. Conference version appeared in the proceedings of STACS 2016. Google Scholar
  28. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of full rank algebraic branching programs. TOCT, 11(1):2:1-2:56, 2019. Conference version appeared in the proceedings of CCC 2017. Google Scholar
  29. Neeraj Kayal and Chandan Saha. Lower bounds for sums of products of low arity polynomials. Electronic Colloquium on Computational Complexity (ECCC), 22:73, 2015. URL: http://eccc.hpi-web.de/report/2015/073.
  30. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth-four formulas with low individual degree. Theory of Computing, 14(1):1-46, 2018. Conference version appeared in the proceedings of STOC 2016. Google Scholar
  31. Adam Klivans and Amir Shpilka. Learning arithmetic circuits via partial derivatives. In Proceedings of the 16th Conference on Learning Theory, COLT 2003, pages 463-476, 2003. Google Scholar
  32. Mrinal Kumar and Shubhangi Saraf. On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM J. Comput., 46(1):336-387, 2017. Google Scholar
  33. J. M Landsberg. Geometric complexity theory: an introduction for geometers. Annali Dell'Universita' Di Ferrara, 61(1):65-117, 2015. Google Scholar
  34. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. Google Scholar
  35. Ketan Mulmuley and Milind A. Sohoni. Geometric complexity theory I: an approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526, 2001. Google Scholar
  36. Ketan Mulmuley and Milind A. Sohoni. Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. Google Scholar
  37. Janaky Murthy, Vineet Nair, and Chandan Saha. Randomized polynomial-time equivalence between determinant and trace-imm equivalence tests. Electronic Colloquium on Computational Complexity (ECCC), 27:91, 2020. Google Scholar
  38. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Symposium on Theory of Computing, STOC 1991, pages 410-418, 1991. Google Scholar
  39. Noam Nisan and Avi Wigderson. Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity, 6(3):217-234, 1997. Google Scholar
  40. Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, pages 33-48, 1996. Google Scholar
  41. Lajos Rónyai. Simple algebras are difficult. In Proceedings of the 19th Symposium on Theory of Computing, STOC 1987, pages 398-408, 1987. Google Scholar
  42. Lajos Rónyai. Computing the structure of finite algebras. J. Symb. Comput., 9(3):355-373, 1990. Google Scholar
  43. Lajos Rónyai. Algorithmic properties of maximal orders in simple algebras over ℚ. Computational Complexity, 2:225–243, 1992. Google Scholar
  44. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. Google Scholar
  45. Nitin Saxena. Morphisms of rings and applications to complexity. PhD thesis, Indian Institute of Technology, Kanpur, 2006. Google Scholar
  46. Jean-Pierre Serre. A Course in Arithmetic. Springer-Verlag New York, 1973. Google Scholar
  47. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  48. Thomas Thierauf. The isomorphism problem for read-once branching programs and arithmetic circuits. Chicago J. Theor. Comput. Sci., 1998, 1998. Google Scholar
  49. Leslie G. Valiant. Completeness classes in algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261. ACM, 1979. Google Scholar
  50. Lars Ambrosius Wallenborn. Computing the hilbert symbol, quadratic form equivalence and integer factoring. Diploma thesis, University of Bonn, 2013. Google Scholar
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