Quadratic lower bound for permanent vs. determinant in any characteristic

DOI10.1007/S00037-009-0284-2MaRDI QIDQ623498zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Xi Chen, Dong Li

Publication date 7 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-009-0284-2

zbMATH Keywords

determinantfinite fieldpermanentarithmetic complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A note on the determinant and permanent problem
• scientific article; zbMATH DE number 2151804
• scientific article; zbMATH DE number 5057518
• Permanent v. determinant: an exponential lower bound assuming symmetry
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture

Cited in

(12)

• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• A note on the determinant and permanent problem
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• A lower bound on determinantal complexity
• Determinants vs. algebraic branching programs
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• A quadratic lower bound for algebraic branching programs
• Algebraic complexity classes
• No occurrence obstructions in geometric complexity theory
• Determinantal complexities and field extensions
• Quadratic lower bounds for algebraic branching programs and formulas
• A quadratic lower bound for homogeneous algebraic branching programs

This page was built for publication: Quadratic lower bound for permanent vs. determinant in any characteristic

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