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
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
