Permanent V. Determinant: An Exponential Lower Bound Assuming Symmetry
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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