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

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.

authors

• Landsberg, Joseph

published proceedings

• DIFFERENTIAL GEOMETRY AND ITS APPLICATIONS

author list (cited authors)

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

citation count

• 2

complete list of authors

• Landsberg, JM||Ressayre, Nicolas

publication date

• January 2017

publisher

• Elsevier  Publisher

published in

• Differential Geometry and Its Applications  Journal

keywords

• Determinant
• Geometric Complexity Theory
• Permanent

Digital Object Identifier (DOI)

• 10.1016/j.difgeo.2017.03.017

start page

• 146

end page

• 166

volume

• 55

URL

• http://dx.doi.org/10.1016/j.difgeo.2017.03.017