Quadratic lower bound for permanent vs. determinant in any characteristic

DOI10.1007/s00037-009-0284-2zbMath1204.68100OpenAlexW1984455600MaRDI QIDQ623498

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

zbMATH Keywords

finite fielddeterminantpermanentarithmetic complexity

Mathematics Subject Classification ID

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

Related Items (8)

Quadratic lower bounds for algebraic branching programs and formulas ⋮ Rectangular Kronecker coefficients and plethysms in geometric complexity theory ⋮ Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture ⋮ No occurrence obstructions in geometric complexity theory ⋮ Algebraic Complexity Classes ⋮ A quadratic lower bound for algebraic branching programs ⋮ A quadratic lower bound for homogeneous algebraic branching programs ⋮ A lower bound on determinantal complexity

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