Quadratic lower bound for permanent vs. determinant in any characteristic

DOI10.1007/S00037-009-0284-2zbMATH Open1204.68100OpenAlexW1984455600MaRDI QIDQ623498FDOQ623498

Xi Chen, Jin-Yi Cai, 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

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

zbMATH Keywords

determinantfinite fieldpermanentarithmetic complexity

Mathematics Subject Classification ID

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

Cited In (11)

• Algebraic Complexity Classes
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• A note on the determinant and permanent problem
• Title not available (Why is that?)
• 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
• No occurrence obstructions in geometric complexity theory
• 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)