On hard instances of non-commutative permanent

DOI10.1016/J.DAM.2019.09.003MaRDI QIDQ2306589zbMATH OpenOpenAlexWikidataFDO

Authors Christian Engels, B. V. Raghavendra Rao

Publication date 23 March 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.09.003

zbMATH Keywords

arithmetic circuit complexitynon-commutativepermanent

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On hard instances of non-commutative permanent
• On the hardness of the noncommutative determinant
• On the hardness of the noncommutative determinant
• Almost settling the hardness of noncommutative determinant
• On explicit branching programs for the rectangular determinant and permanent polynomials

Cites work

• Algebras with Polynomial Identities and Computing the Determinant
• Arithmetic circuits and the Hadamard product of polynomials
• Arithmetic circuits: a survey of recent results and open questions
• Completeness and reduction in algebraic complexity theory
• Computational Complexity
• Feasible arithmetic computations: Valiant's hypothesis
• Noncommutativity makes determinants hard
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the hardness of approximate reasoning
• On the hardness of the noncommutative determinant
• Planarity, determinants, permanents, and (unique) matchings
• Quaternionic determinants
• Random interval graphs
• Small space analogues of Valiant's classes and the limitations of skew formulas
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(4)

• On hard instances of non-commutative permanent
• On explicit branching programs for the rectangular determinant and permanent polynomials
• On the hardness of the noncommutative determinant
• On the hardness of the noncommutative determinant

This page was built for publication: On hard instances of non-commutative permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2306589)