Noncommutativity makes determinants hard

DOI10.1016/J.IC.2014.12.010MaRDI QIDQ2347802zbMATH OpenOpenAlexFDO

Authors Markus Bläser

Publication date 9 June 2015

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2014.12.010

zbMATH Keywords

determinantcounting complexitypermanentassociative algebras

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15)

Recommendations

• Noncommutativity makes determinants hard
• On the hardness of the noncommutative determinant
• On the hardness of the noncommutative determinant
• Almost settling the hardness of noncommutative determinant
• Determinants of matrices over noncommutative rings
• scientific article; zbMATH DE number 67947
• Non-commutative moment problems
• Determinants of block matrices with noncommuting blocks
• Noncommutative Sylvester's determinantal identity

Cites work

• scientific article; zbMATH DE number 3747179 (Why is no real title available?)
• scientific article; zbMATH DE number 612882 (Why is no real title available?)
• A Monte-Carlo Algorithm for Estimating the Permanent
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Almost settling the hardness of noncommutative determinant
• Approximating the permanent via nonabelian determinants
• Clifford algebras and approximating the permanent
• Complexity and approximability of the cover polynomial
• Complexity of the Cover Polynomial
• Computing Levi decompositions in Lie algebras
• Determinant: Old Algorithms, New Insights
• Efficient decomposition of associative algebras over finite fields
• Efficient decomposition of separable algebras.
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• On the hardness of the noncommutative determinant
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• The complexity of computing the permanent

Cited in

(8)

• The group factorization problem in finite groups of Lie type
• A new family of polynomial identities for computing determinants
• Noncommutativity makes determinants hard
• On the hardness of the noncommutative determinant
• On the hardness of the noncommutative determinant
• On explicit branching programs for the rectangular determinant and permanent polynomials
• Almost settling the hardness of noncommutative determinant
• Algebras with Polynomial Identities and Computing the Determinant

This page was built for publication: Noncommutativity makes determinants hard

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