Permanent v. determinant: an exponential lower bound assuming symmetry

DOI10.1145/2840728.2840735MaRDI QIDQ2800550zbMATH OpenOpenAlexFDO

Authors Nicolas Ressayre, J. M. Landsberg

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

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)

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

Cited in

(8)

• A study of the representations supported by the orbit closure of the determinant
• On Leonid Gurvits's proof for permanents
• Quadratic lower bound for permanent vs. determinant in any characteristic
• Permanent and determinant
• A note on the determinant and permanent problem
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Permanent versus determinant: not via saturations
• Symmetric determinantal representation of formulas and weakly skew circuits

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)