Document Open Access Logo

Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time

Authors V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.23.pdf
  • Filesize: 0.71 MB
  • 22 pages

Document Identifiers

Author Details

V. Arvind
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Abhranil Chatterjee
  • Indian Institute of Technology Bombay, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, India

Acknowledgements

We thank the anonymous reviewers of an earlier version for their valuable comments that have helped us to improve the presentation.

Cite As Get BibTex

V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay. Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.23

Abstract

Hrubeš and Wigderson [Hrubeš and Wigderson, 2015] initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, there are deterministic polynomial-time algorithms due to Garg, Gurvits, Oliveira, and Wigderson [Ankit Garg et al., 2016] and Ivanyos, Qiao, and Subrahmanyam [Ivanyos et al., 2018].
A central open problem in this area is to design an efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including concepts from matrix coefficient realization theory [Volčič, 2018] and properties of cyclic division algebras [T.Y. Lam, 2001]. En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas [Michael A. Forbes and Amir Shpilka, 2013] inside a cyclic division algebra of small index.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation
Keywords
  • Rational Identity Testing
  • Black-box Derandomization
  • Cyclic Division Algebra
  • Matrix coefficient realization theory

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669-697, 2015. URL: https://doi.org/10.1137/140975103.
  2. S.A Amitsur. Rational identities and applications to algebra and geometry. Journal of Algebra, 3(3):304-359, 1966. URL: https://doi.org/10.1016/0021-8693(66)90004-4.
  3. V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.10.
  4. George M Bergman. Rational relations and rational identities in division rings. Journal of Algebra, 43(1):252-266, 1976. https://doi.org/10.1016/0021-8693(76)90159-9.
  5. 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.
  6. 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.
  7. 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.
  8. Samuel Eilenberg. Automata, Languages, and Machines (Vol A). Pure and Applied Mathematics. Academic Press, 1974. Google Scholar
  9. 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.
  10. Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, and Avi Wigderson. A deterministic polynomial time algorithm for non-commutative rational identity testing. 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 109-117. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.95.
  11. Pavel Hrubeš and Avi Wigderson. Non-commutative arithmetic circuits with division. Theory of Computing, 11(14):357-393, 2015. URL: https://doi.org/10.4086/toc.2015.v011a014.
  12. 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.
  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. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  15. T.Y. Lam. A First Course in Noncommutative Rings (Second Edition). Graduate Texts in Mathematics. Springer, 2001. Google Scholar
  16. 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.
  17. Jacob T. Schwartz. Fast probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701-717, 1980. Google Scholar
  18. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. URL: http://eudml.org/doc/151394.
  19. Jurij Volčič. Matrix coefficient realization theory of noncommutative rational functions. Journal of Algebra, 499:397-437, April 2018. URL: https://doi.org/10.1016/j.jalgebra.2017.12.009.
  20. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact