Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture Academic Article uri icon


  • 2017 Elsevier B.V. We initiate a study of determinantal representations with symmetry. We show that Grenet's determinantal representation for the permanent is optimal among determinantal representations equivariant with respect to left multiplication by permutation and diagonal matrices (roughly half the symmetry group of the permanent). We introduce a restricted model of computation, equivariant determinantal complexity, and prove an exponential separation of the permanent and the determinant in this model. This is the first exponential separation of the permanent from the determinant in any restricted model.

published proceedings

  • Differential Geometry and its Applications

author list (cited authors)

  • Landsberg, J. M., & Ressayre, N.

citation count

  • 1

complete list of authors

  • Landsberg, JM||Ressayre, Nicolas

publication date

  • December 2017