New results on noncommutative and commutative polynomial identity testing

DOI10.1007/S00037-010-0299-8MaRDI QIDQ626693zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70)

Recommendations

• Randomized polynomial time identity testing for noncommutative circuits
• scientific article; zbMATH DE number 7140484
• Deterministic polynomial identity testing in non-commutative models
• Non-commutative computations: lower bounds and polynomial identity testing

Cited in

(12)

• Randomized polynomial time identity testing for noncommutative circuits
• Non-commutative computations: lower bounds and polynomial identity testing
• Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
• A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.
• Derandomizing isolation in space-bounded settings
• Multivariate to bivariate reduction for noncommutative polynomial factorization
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Efficient Black-Box Identity Testing for Free Group Algebras
• scientific article; zbMATH DE number 7204372 (Why is no real title available?)
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Random arithmetic formulas can be reconstructed efficiently
• Deterministically testing sparse polynomial identities of unbounded degree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626693)