Witnessing matrix identities and proof complexity

DOI10.1142/S021819671850011XzbMath1417.16029OpenAlexW2787461463MaRDI QIDQ4634922

Iddo Tzameret, Fu Li

Publication date: 12 April 2018

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s021819671850011x

zbMATH Keywords

algebraic complexityproof complexityPI-algebrasnon-commutative circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) (T)-ideals, identities, varieties of associative rings and algebras (16R10) Complexity of proofs (03F20)

Related Items (2)

Characterizing Propositional Proofs as Noncommutative Formulas ⋮ On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices

Cites Work

• Kemer's theorem for affine PI algebras over a field of characteristic zero.
• Algebraic proofs over noncommutative formulas
• Deterministic polynomial identity testing in non-commutative models
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The relative efficiency of propositional proof systems
• Multilinear Identities of the Matrix Ring
• Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
• Randomized polynomial time identity testing for noncommutative circuits
• Short Proofs for the Determinant Identities
• Algebras with Polynomial Identities and Computing the Determinant
• Minimal Identities for Algebras
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Witnessing matrix identities and proof complexity