On the complexity of noncommutative polynomial factorization

DOI10.1016/j.ic.2018.05.009zbMath1400.68080arXiv1501.00671OpenAlexW2888805838MaRDI QIDQ1784944

Gaurav Rattan, V. Arvind, Pushkar S. Joglekar

Publication date: 27 September 2018

Published in: Information and Computation, Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.00671

zbMATH Keywords

polynomial factorizationcomplexity classesarithmetic circuitsnoncommutative polynomialsidentity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.) (16S10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Geometry of free loci and factorization of noncommutative polynomials ⋮ On the factorization of non-commutative polynomials (in free associative algebras) ⋮ On the complexity of noncommutative polynomial factorization ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New results on noncommutative and commutative polynomial identity testing
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Deterministic polynomial identity testing in non-commutative models
• On the complexity of noncommutative polynomial factorization
• The complexity of matrix rank and feasible systems of linear equations
• Equivalence of polynomial identity testing and polynomial factorization
• Polynomial Decompositions in Polynomial Time
• Arithmetic Circuits: A survey of recent results and open questions
• Tensor rank is NP-complete
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Learning functions represented as multiplicity automata
• Noncommutative Valiant's Classes
• Noncommutative Unique Factorization Domains

This page was built for publication: On the complexity of noncommutative polynomial factorization