On the hardness of the noncommutative determinant

DOI10.1007/s00037-016-0148-5zbMath1390.68319OpenAlexW2559420014MaRDI QIDQ5916037

Srikanth Srinivasan, V. Arvind

Publication date: 18 April 2018

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-016-0148-5

zbMATH Keywords

determinantpermanentnoncommutative arithmetic circuitspermanent estimators

Mathematics Subject Classification ID

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)

Related Items (2)

Fast exact algorithms using Hadamard product of polynomials ⋮ A super-quadratic lower bound for depth four arithmetic circuits

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Gap-definable counting classes
• Quaternionic determinants
• Deterministic polynomial identity testing in non-commutative models
• Noncommutativity makes determinants hard
• Approximating the Permanent via Nonabelian Determinants
• Arithmetic Circuits and the Hadamard Product of Polynomials
• A Monte-Carlo Algorithm for Estimating the Permanent
• Almost settling the hardness of noncommutative determinant
• Algebras with Polynomial Identities and Computing the Determinant
• On the hardness of the noncommutative determinant
• Counting classes: Thresholds, parity, mods, and fewness
• Clifford algebras and approximating the permanent

This page was built for publication: On the hardness of the noncommutative determinant