Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture

DOI10.1016/j.difgeo.2017.03.017zbMath1380.68202arXiv1508.05788OpenAlexW1912131999WikidataQ115355484 ScholiaQ115355484MaRDI QIDQ1679675

Nicolas Ressayre, Joseph M. Landsberg

Publication date: 21 November 2017

Published in: Differential Geometry and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.05788

zbMATH Keywords

determinantpermanentgeometric complexity theory

Mathematics Subject Classification ID

Related Items (5)

Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices ⋮ On the complexity of the permanent in various computational models ⋮ A lower bound on determinantal complexity ⋮ The Waring Rank of the 3 x 3 Permanent

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characters of projective representations of symmetric groups
• Quadratic lower bound for permanent vs. determinant in any characteristic
• The permanent of a square matrix
• On the relation between the determinant and the permanent
• Primary ideals associated to the linear strands of Lascoux's resolution and syzygies of the corresponding irreducible representations of the Lie superalgebra \(\mathfrak {gl}(m|n)\)
• Permanent and determinant
• Shifted tableaux and the projective representations of symmetric groups
• A note on the determinant and permanent problem
• Representing Boolean functions as polynomials modulo composite numbers
• On the complexity of the permanent in various computational models
• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
• A lower bound for the determinantal complexity of a hypersurface
• On the rank of a symmetric form
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Short monotone formulae for the majority function
• The Permanent Function
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Sums of Like Powers of Multivariate Linear Forms
• Power sum decompositions of elementary symmetric polynomials

This page was built for publication: Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture