Noncommutativity makes determinants hard
From MaRDI portal
Publication:2347802
DOI10.1016/j.ic.2014.12.010zbMath1327.68124OpenAlexW2053708783MaRDI QIDQ2347802
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
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
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