On Hard Instances of Non-Commutative Permanent

DOI10.1007/978-3-319-42634-1_14zbMath1477.68118OpenAlexW2498618480MaRDI QIDQ2817859

B. V. Raghavendra Rao, Christian Engels

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_14

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Feasible arithmetic computations: Valiant's hypothesis
• Quaternionic determinants
• Completeness and reduction in algebraic complexity theory
• Small space analogues of Valiant's classes and the limitations of skew formulas
• Arithmetic Circuits and the Hadamard Product of Polynomials
• Arithmetic Circuits: A survey of recent results and open questions
• Two Algorithmic Results for the Traveling Salesman Problem
• Computational Complexity
• Noncommutativity Makes Determinants Hard
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Algebras with Polynomial Identities and Computing the Determinant
• On the hardness of the noncommutative determinant
• Planarity, Determinants, Permanents, and (Unique) Matchings

This page was built for publication: On Hard Instances of Non-Commutative Permanent