Permanent v. determinant: an exponential lower bound assuming symmetry

DOI10.1145/2840728.2840735zbMATH Open1334.68090OpenAlexW2293763217MaRDI QIDQ2800550FDOQ2800550

J. M. Landsberg, Nicolas Ressayre

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2840728.2840735

Recommendations

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

zbMATH Keywords

determinantpermanentgeometric complexity theory

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15)

Cited In (4)

• Permanent and determinant
• A note on the determinant and permanent problem
• Quadratic lower bound for permanent vs. determinant in any characteristic
• On Leonid Gurvits's proof for permanents

This page was built for publication: Permanent v. determinant: an exponential lower bound assuming symmetry

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