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

abstract

  • © 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.

author list (cited authors)

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

citation count

  • 0

publication date

  • December 2017