Algebras with Polynomial Identities and Computing the Determinant

DOI10.1137/S0097539705447359zbMath1142.68033MaRDI QIDQ5454251

Steve Chien, Alistair Sinclair

Publication date: 28 March 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

determinantspermanentspolynomial identitiesalgebraic branching programsalgebraic computationcomplexity lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Identities other than those of matrices over commutative rings (16R40)

Related Items (8)

Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Witnessing matrix identities and proof complexity ⋮ On the hardness of the noncommutative determinant ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Unnamed Item ⋮ On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

This page was built for publication: Algebras with Polynomial Identities and Computing the Determinant