A note on the determinant and permanent problem

DOI10.1016/0890-5401(90)90036-HzbMath0687.68021OpenAlexW2115574407MaRDI QIDQ1263283

Jin-Yi Cai

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90036-h

zbMATH Keywords

lower boundaffine linear transformationsdeterminant and permanent problemValiant's theory of arithmetic complexity

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) Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items

\(P\) versus \(NP\) and geometry, On the Pólya permanent problem over finite fields, Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture, Are there elimination algorithms for the permanent?, Depth-4 lower bounds, determinantal complexity: a unified approach, Algebraic Complexity Classes, A lower bound on determinantal complexity

Cites Work

• The complexity of computing the permanent
• On the relation between the determinant and the permanent
• Permanent and determinant
• The solution of van der Waerden's problem for permanents
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item