Permanent V. Determinant: An Exponential Lower Bound Assuming Symmetry Conference Paper uri icon

abstract

  • Grenet's determinantal representation for the permanent is optimal among determinantal representations that are equivariant with respect to left multiplication by permutation and diagonal matrices (roughly half the symmetry group of the permanent). In particular, if any optimal determinantal representation of the permanent must be polynomially related to one with such symmetry, then Valiant's conjecture on permanent v. determinant is true.

name of conference

  • Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science

published proceedings

  • ITCS'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON INNOVATIONS IN THEORETICAL COMPUTER SCIENCE

author list (cited authors)

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

citation count

  • 2

complete list of authors

  • Landsberg, Joseph M||Ressayre, Nicolas

editor list (cited editors)

  • Sudan, M.

publication date

  • January 2016