A note on the determinant and permanent problem

DOI10.1016/0890-5401(90)90036-HMaRDI QIDQ1263283zbMATH OpenOpenAlexFDO

Authors 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

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Polynomials in general fields (irreducibility, etc.) (12E05)

Recommendations

• scientific article; zbMATH DE number 2151804
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Permanent and determinant
• scientific article; zbMATH DE number 5057518
• Permanent v. determinant: an exponential lower bound assuming symmetry

Cites work

• scientific article; zbMATH DE number 3744549 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 3621932 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• On the relation between the determinant and the permanent
• Permanent and determinant
• The complexity of computing the permanent
• The solution of van der Waerden's problem for permanents

Cited in

(23)

• On the complexity of the permanent in various computational models
• Upper bounds on real roots and lower bounds for the permanent
• On Leonid Gurvits's proof for permanents
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Binary determinantal complexity
• Depth-4 lower bounds, determinantal complexity: a unified approach
• On the Pólya conversion problem for permanents and determinants
• Permanent and determinant
• 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
• \(P\) versus \(NP\) and geometry
• Permanent versus determinant: not via saturations
• scientific article; zbMATH DE number 3856393 (Why is no real title available?)
• A note on perfect partial elimination
• Are there elimination algorithms for the permanent?
• scientific article; zbMATH DE number 5057518 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• Algebraic complexity classes
• Affine projections of polynomials (extended abstract)
• Solutions to two problems on permanents
• A lower bound on determinantal complexity
• On two extremal matrix problems
• Permanent v. determinant: an exponential lower bound assuming symmetry

This page was built for publication: A note on the determinant and permanent problem

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