New results on noncommutative and commutative polynomial identity testing

DOI10.1007/S00037-010-0299-8zbMATH Open1225.68090OpenAlexW2172695686MaRDI QIDQ626693FDOQ626693

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

Recommendations

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

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)

Cited In (12)

• A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.
• Derandomizing Isolation in Space-Bounded Settings
• Efficient Black-Box Identity Testing for Free Group Algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• On the complexity of noncommutative polynomial factorization
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Deterministically testing sparse polynomial identities of unbounded degree
• Random arithmetic formulas can be reconstructed efficiently
• Multivariate to bivariate reduction for noncommutative polynomial factorization
• Sparse multivariate polynomial interpolation on the basis of Schubert polynomials

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)