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

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.