New results on noncommutative and commutative polynomial identity testing

DOI10.1007/s00037-010-0299-8zbMath1225.68090OpenAlexW2172695686MaRDI QIDQ626693

Srikanth Srinivasan, V. Arvind, Partha Mukhopadhyay

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-010-0299-8

zbMATH Keywords

automata theorypolynomial identity testingnoncommutative arithmetic circuits

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Unnamed Item ⋮ Sparse multivariate polynomial interpolation on the basis of Schubert polynomials ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ Efficient Black-Box Identity Testing for Free Group Algebras ⋮ On the complexity of noncommutative polynomial factorization ⋮ Unnamed Item ⋮ A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

This page was built for publication: New results on noncommutative and commutative polynomial identity testing