LIPIcs.MFCS.2017.38.pdf
- Filesize: 0.49 MB
- 13 pages
Document
Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings
Authors
-
Part of:
Volume:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-01
Cite As Get BibTex
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.38
Abstract
In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring F{X}. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff, and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing and Polynomial Factorization in F{X} and show the following results.
1. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give a deterministic polynomial algorithm to decide if f is identically zero. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz and Shpilka for noncommutative ABPs.
2. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of f in polynomial time when F is the field of rationals. Over finite fields of characteristic p,
our algorithm runs in time polynomial in input size and p.
Subject Classification
Keywords
- Circuits
- Nonassociative
- Noncommutative
- Polynomial Identity Testing
- Factorization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Avraham Shimshon Amitsur and Jacob Levitzki. Minimal identities for algebras. Proceedings of the American Mathematical Society, 1(4):449-463, 1950.
- Vikraman Arvind, Pushkar S. Joglekar, and Gaurav Rattan. On the complexity of noncommutative polynomial factorization. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 38-49, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48054-0_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: http://dx.doi.org/10.1007/s00037-010-0299-8.
-
Vikraman Arvind and S. Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago J. Theor. Comput. Sci., 2016 (6), 2016.
- E. R. Berlekamp. Factoring polynomials over large finite fields*. In Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation, SYMSAC'71, pages 223-, New York, NY, USA, 1971. ACM. URL: http://dx.doi.org/10.1145/800204.806290.
-
P.M. Cohn. Noncommutative unique factorization domains. Transactions of the American Math. Society, 109(2):313-331, 1963.
- Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Relationless completeness and separations. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 280-290, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.34.
- Laurent Hyafil. The power of commutativity. In 18th Annual Symposium on Foundations of Computer Science (FOCS), Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 171-174, 1977. URL: http://dx.doi.org/10.1109/SFCS.1977.31.
-
Erich Kaltofen. Factorization of polynomials given by straight-line programs. Randomness in Computation, vol. 5 of Advances in Computing Research:375–412, 1989.
- Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and polynomial factorization. Computational Complexity, 24(2):295-331, 2015. URL: http://dx.doi.org/10.1007/s00037-015-0102-y.
- Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 23:94, 2016. URL: http://eccc.hpi-web.de/report/2016/094.
- Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In STOC, pages 410-418, 1991. URL: http://dx.doi.org/10.1145/103418.103462.
- Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1-19, 2005. URL: http://dx.doi.org/10.1007/s00037-005-0188-8.
- 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. URL: http://dx.doi.org/10.1561/0400000039.
-
Joachim von zur Gathen and Victor Shoup. Computing frobenius maps and factoring polynomials. Computational Complexity, 2:187-224, 1992.