Noncommutativity makes determinants hard

DOI10.1016/j.ic.2014.12.010zbMath1327.68124OpenAlexW2053708783MaRDI QIDQ2347802

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

determinantpermanentcounting complexityassociative algebras

Mathematics Subject Classification ID

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

Related Items

Unnamed Item, On the hardness of the noncommutative determinant

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity and approximability of the cover polynomial
• The complexity of computing the permanent
• Computing Levi decompositions in Lie algebras
• Efficient decomposition of separable algebras.
• Efficient decomposition of associative algebras over finite fields
• Approximating the Permanent via Nonabelian Determinants
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• A Monte-Carlo Algorithm for Estimating the Permanent
• Determinant: Old Algorithms, New Insights
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Almost settling the hardness of noncommutative determinant
• Complexity of the Cover Polynomial
• On the hardness of the noncommutative determinant
• Clifford algebras and approximating the permanent