Noncommutativity makes determinants hard
DOI10.1016/J.IC.2014.12.010zbMATH Open1327.68124OpenAlexW2053708783MaRDI QIDQ2347802FDOQ2347802
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
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
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)
Cites Work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- The complexity of computing the permanent
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- A Monte-Carlo Algorithm for Estimating the Permanent
- Title not available (Why is that?)
- Efficient decomposition of associative algebras over finite fields
- Title not available (Why is that?)
- Complexity and approximability of the cover polynomial
- Efficient decomposition of separable algebras.
- Complexity of the Cover Polynomial
- Approximating the permanent via nonabelian determinants
- On the hardness of the noncommutative determinant
- Determinant: Old Algorithms, New Insights
- Clifford algebras and approximating the permanent
- Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
- Computing Levi decompositions in Lie algebras
- Almost settling the hardness of noncommutative determinant
Cited In (8)
- The group factorization problem in finite groups of Lie type
- A new family of polynomial identities for computing determinants
- On the hardness of the noncommutative determinant
- On the hardness of the noncommutative determinant
- Algebras with Polynomial Identities and Computing the Determinant
- On explicit branching programs for the rectangular determinant and permanent polynomials
- Almost settling the hardness of noncommutative determinant
- Noncommutativity makes determinants hard
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)
