Efficient Black-Box Identity Testing for Free Group Algebras

Authors V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.57.pdf
  • Filesize: 489 kB
  • 16 pages

Document Identifiers

Author Details

V. Arvind
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Abhranil Chatterjee
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Rajit Datta
  • Chennai Mathematical Institute, Chennai, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, Chennai, India

Acknowledgements

We thank the anonymous reviewers of RANDOM 2019 for their valuable comments.

Cite AsGet BibTex

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Efficient Black-Box Identity Testing for Free Group Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.57

Abstract

Hrubeš and Wigderson [Pavel Hrubeš and Avi Wigderson, 2014] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. For noncommutative formulas with inverses the problem can be solved in deterministic polynomial time in the white-box model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the black-box model [Harm Derksen and Visu Makam, 2017], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions, in general, remains open for noncommutative circuits with inverses. We solve the problem for a natural special case. We consider expressions in the free group algebra F(X,X^{-1}) where X={x_1, x_2, ..., x_n}. Our main results are the following. 1) Given a degree d expression f in F(X,X^{-1}) as a black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an Amitsur-Levitzki type theorem [A. S. Amitsur and J. Levitzki, 1950] for F(X, X^{-1}). This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression. 2) Given an expression f in F(X,X^{-1}) of degree D and sparsity s, as black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomial-time algorithm when D and s are exponential in n.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation
Keywords
  • Rational identity testing
  • Free group algebra
  • Noncommutative computation
  • Randomized algorithms

Metrics

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

References

  1. A. S. Amitsur and J. Levitzki. Minimal Identities for Algebras. Proceedings of the American Mathematical Society, 1(4):449-463, 1950. URL: http://www.jstor.org/stable/2032312.
  2. 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.
  3. Vikraman Arvind and Partha Mukhopadhyay. The ideal membership problem and polynomial identity testing. Inf. Comput., 208(4):351-363, 2010. URL: https://doi.org/10.1016/j.ic.2009.06.003.
  4. 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.
  5. George M Bergman. Rational relations and rational identities in division rings. Journal of Algebra, 43(1):252-266, 1976. URL: https://doi.org/10.1016/0021-8693(76)90159-9.
  6. 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.
  7. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  8. Harm Derksen and Visu Makam. Polynomial degree bounds for matrix semi-invariants. Advances in Mathematics, 310:44-63, 2017. URL: https://doi.org/10.1016/j.aim.2017.01.018.
  9. Michael Forbes and Amir Shpilka. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Foundations of Computer Science, 1975., 16th Annual Symposium on, September 2012. URL: https://doi.org/10.1109/FOCS.2013.34.
  10. 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
  11. Pavel Hrubes and Amir Yehudayoff. Arithmetic Complexity in Ring Extensions. Theory of Computing, 7:119-129, 2011. Google Scholar
  12. Pavel Hrubeš and Avi Wigderson. Non-commutative arithmetic circuits with division. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 49-66, 2014. URL: https://doi.org/10.1145/2554797.2554805.
  13. 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. URL: https://doi.org/10.1007/s00037-018-0165-7.
  14. 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. URL: https://doi.org/10.1145/380752.380801.
  15. Tsiu-Kwen Lee and Yiqiang Zhou. Right ideals generated by an idempotent of finite rank. Linear Algebra and its Applications, 431:2118-2126, November 2009. URL: https://doi.org/10.1016/j.laa.2009.07.005.
  16. 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.
  17. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. URL: https://doi.org/10.1007/s00037-005-0188-8.
  18. Louis Halle Rowen. Polynomial identities in ring theory. Pure and Applied Mathematics. Academic Press, 1980. Google Scholar
  19. Jacob T. Schwartz. Fast Probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701-717, 1980. Google Scholar
  20. Volker Strassen. Vermeidung von Divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. URL: http://eudml.org/doc/151394.
  21. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pages 216-226, 1979. 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