Witnessing matrix identities and proof complexity

DOI10.1142/S021819671850011XMaRDI QIDQ4634922zbMATH OpenOpenAlexFDO

Authors Fu Li, Iddo Tzameret

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 complexitynon-commutative circuitsPI-algebrasproof complexity

Mathematics Subject Classification ID

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

Recommendations

• The proof complexity of linear algebra
• Short proofs for the determinant identities
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• Algebras with Polynomial Identities and Computing the Determinant
• The power of depth 2 circuits over algebras

Cites work

• Algebraic proofs over noncommutative formulas
• Algebras with Polynomial Identities and Computing the Determinant
• Arithmetic complexity in ring extensions
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic polynomial identity testing in non-commutative models
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 4053838 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3721092 (Why is no real title available?)
• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• scientific article; zbMATH DE number 2079090 (Why is no real title available?)
• scientific article; zbMATH DE number 6829288 (Why is no real title available?)
• scientific article; zbMATH DE number 1358157 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• Kemer's theorem for affine PI algebras over a field of characteristic zero.
• Minimal Identities for Algebras
• Multilinear Identities of the Matrix Ring
• Randomized polynomial time identity testing for noncommutative circuits
• Short Proofs for the Determinant Identities
• The relative efficiency of propositional proof systems

Cited in

(3)

• Witnesses for Boolean matrix multiplication and for transitive closure
• On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices
• Characterizing propositional proofs as noncommutative formulas

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

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