Fall 2014

Permanent versus Determinant: An Exponential Lower Bound Assuming Symmetry and a Potential Path towards Valiant's Conjecture

Monday, Dec. 14, 2015 9:00 am9:45 am PST

Add to Calendar


Calvin Lab

L. Valiant conjectured that a polynomial that is "easy" to write down, is not necessarily "easy" to evaluate. More precisely,  he conjectured that the permanent polynomial of an mxm matrix cannot be written as the determinant of an nxn matrix whose entries are affine linear forms in the entries of the mxm matrix when n is a polynomial in m.  I will explain how one can prove Valiant's conjecture under a symmetry hypothesis and how this result reveals new approaches to the conjecture. This is joint work with N. Ressayre.