Non-commutative computations: lower bounds and polynomial identity testing

DOI10.4086/CJTCS.2019.002MaRDI QIDQ5232538zbMATH OpenOpenAlexFDO

Authors Guillaume Lagarde, Sylvain Perifel, Guillaume Malod

Publication date 12 September 2019

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2019.002

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Deterministic polynomial identity testing in non-commutative models
• scientific article; zbMATH DE number 7140484
• Randomized polynomial time identity testing for noncommutative circuits
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Arithmetic circuits: a survey of recent results and open questions

Cites work

• A probabilistic remark on algebraic program testing
• Arithmetic circuits: a survey of recent results and open questions
• Characterizing Valiant's algebraic complexity classes
• Clifford algebras and approximating the permanent
• Deterministic polynomial identity testing in non-commutative models
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Lower bounds for arithmetic circuits via the Hankel matrix
• Matrices de Hankel
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• New results on noncommutative and commutative polynomial identity testing
• Realizations by stochastic finite automata

Cited in

(12)

• Lower bounds for arithmetic circuits via the Hankel matrix
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• The complexity of bounded register and skew arithmetic computation
• Arithmetic circuits: a survey of recent results and open questions
• scientific article; zbMATH DE number 6829271 (Why is no real title available?)
• Randomized polynomial time identity testing for noncommutative circuits
• Quasipolynomial hitting sets for circuits with restricted parse trees
• scientific article; zbMATH DE number 7204372 (Why is no real title available?)
• scientific article; zbMATH DE number 7204375 (Why is no real title available?)
• scientific article; zbMATH DE number 7140484 (Why is no real title available?)
• New results on noncommutative and commutative polynomial identity testing
• Efficient polynomial identity testing over nonassociative algebras

This page was built for publication: Non-commutative computations: lower bounds and polynomial identity testing

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