Document Open Access Logo

On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

Authors V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, C. Ramya

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.6.pdf
  • Filesize: 0.78 MB
  • 23 pages

Document Identifiers

Author Details

V. Arvind
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Abhranil Chatterjee
  • National Institute of Science Education and Research (HBNI), Bhubaneswar, India
Utsab Ghosal
  • Chennai Mathematical Institute, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, India
C. Ramya
  • Institute of Mathematical Sciences (HBNI), Chennai, India

Funding

  • Ghosal, Utsab: Partially supported by Infosys Foundation.
  • Mukhopadhyay, Partha: Partially supported by Infosys Foundation.

Acknowledgements

We thank the anonymous reviewers for their feedback. This work was done when the second author was a postdoctoral researcher at IIT Bombay.

Cite AsGet BibTex

V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.6

Abstract

The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables [Hrubeš and Wigderson, 2015]. This rank computation problem has deterministic polynomial-time white-box algorithms [Ankit Garg et al., 2016; Ivanyos et al., 2018] and a randomized polynomial-time algorithm in the black-box setting [Harm Derksen and Visu Makam, 2017]. In this paper, we propose a new approach for efficient derandomization of black-box RIT. Additionally, we obtain results for matrix rank computation over the free skew field and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show: - Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the k×k matrix algebra is 2^Ω(k) [Andrej Bogdanov and Hoeteck Wee, 2005], we obtain a subexponential-time black-box RIT algorithm for rational formulas of inversion height almost logarithmic in the size of the formula. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. - We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. While an efficient rank computation was known for matrices with noncommutative formulas as entries [Ankit Garg et al., 2020], we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. - Motivated by the definition given by Bergman [George M Bergman, 1976], we define a new class of rational functions where a rational function of inversion height at most h is defined as a composition of a noncommutative r-skewed circuit (equivalently an ABP) with inverses of rational functions of this class of inversion height at most h-1 which are also disjoint. We obtain a polynomial-size linear pencil representation for this class which gives a white-box deterministic polynomial-time identity testing algorithm for the class.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic Complexity
  • Identity Testing
  • Non-commutative rank

Metrics

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

Related Versions

References

  1. S.A Amitsur. Rational identities and applications to algebra and geometry. Journal of Algebra, 3(3):304-359, 1966. Google Scholar
  2. Vikraman Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On identity testing and noncommutative rank computation over the free skew field. CoRR, abs/2209.04797, 2022. URL: https://doi.org/10.48550/arXiv.2209.04797.
  3. Vikraman Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay. Black-box identity testing of noncommutative rational formulas of inversion height two in deterministic quasipolynomial-time. CoRR, abs/2202.05693 (to appear in RANDOM 2022), 2022. URL: https://arxiv.org/abs/2202.05693.
  4. Vikraman Arvind and Pushkar S. Joglekar. On efficient noncommutative polynomial factorization via higman linearization. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 12:1-12:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.12.
  5. Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja. Randomized polynomial time identity testing for noncommutative circuits. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 831-841, 2017. URL: https://doi.org/10.1145/3055399.3055442.
  6. Vikraman Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan. New results on noncommutative and commutative polynomial identity testing. Computational Complexity, 19(4):521-558, 2010. URL: https://doi.org/10.1007/s00037-010-0299-8.
  7. George M Bergman. Rational relations and rational identities in division rings. Journal of Algebra, 43(1):252-266, 1976. URL: http://www.sciencedirect.com/science/article/pii/0021869376901599.
  8. J. Berstel and C. Reutenauer. Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2011. URL: https://books.google.co.in/books?id=LL8Nhn72I_8C.
  9. Andrej Bogdanov and Hoeteck Wee. More on noncommutative polynomial identity testing. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 92-99, 2005. URL: https://doi.org/10.1109/CCC.2005.13.
  10. Prerona Chatterjee. Separating abps and some structured formulas in the non-commutative setting. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 7:1-7:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  11. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs randomness for bounded depth arithmetic circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 13:1-13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.13.
  12. P. M. Cohn. The embedding of firs in skew fields. Proceedings of The London Mathematical Society, pages 193-213, 1971. Google Scholar
  13. P. M. Cohn. Skew Fields: Theory of General Division Rings. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1995. Google Scholar
  14. Harm Derksen and Visu Makam. Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics, 310:44-63, 2017. Google Scholar
  15. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: https://doi.org/10.1137/080735850.
  16. Samuel Eilenberg. Automata, Languages, and Machines (Vol A). Pure and Applied Mathematics. Academic Press, 1974. Google Scholar
  17. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. SIAM J. Comput., 50(3), 2021. URL: https://doi.org/10.1137/16M1097870.
  18. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252, 2013. URL: https://doi.org/10.1109/FOCS.2013.34.
  19. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. Operator scaling: Theory and applications. Found. Comput. Math., 20(2):223-290, 2020. URL: https://doi.org/10.1007/s10208-019-09417-z.
  20. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 109-117, 2016. Google Scholar
  21. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute (extended abstract). In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 262-272. ACM, 1980. URL: https://doi.org/10.1145/800141.804674.
  22. Graham Higman. Units in group rings. PhD Thesis. Balliol College, 1940. Google Scholar
  23. Pavel Hrubeš and Avi Wigderson. Non-commutative arithmetic circuits with division. Theory of Computing, 11(14):357-393, 2015. URL: http://www.theoryofcomputing.org/articles/v011a014.
  24. Loo-Keng Hua. Some properties of a sfield. Proceedings of the National Academy of Sciences of the United States of America, 35(9):533-537, 1949. URL: http://www.jstor.org/stable/88328.
  25. Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam. Constructive non-commutative rank computation is in deterministic polynomial time. computational complexity, 27(4):561-593, December 2018. Google Scholar
  26. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1-2):1-46, 2004. Google Scholar
  27. Dmitry S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov. Singularities of rational functions and minimal factorizations: The noncommutative and the commutative setting. Linear Algebra and its Applications, 430(4):869-889, 2009. URL: https://www.sciencedirect.com/science/article/pii/S0024379508003893.
  28. Adam R. Klivans and Daniel Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC '01, pages 216-223, New York, NY, USA, 2001. ACM. Google Scholar
  29. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804-814. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00083.
  30. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418, 1991. URL: https://doi.org/10.1145/103418.103462.
  31. Louis Halle Rowen. Polynomial identities in ring theory. Pure and Applied Mathematics. Academic Press, 1980. URL: http://gen.lib.rus.ec/book/index.php?md5=bde982110d09e6199643e04da0558459.
  32. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. URL: http://eudml.org/doc/151394.
  33. Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 416-425. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520044.
  34. Jurij Volčič. Matrix coefficient realization theory of noncommutative rational functions. Journal of Algebra, 499:397-437, April 2018. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact