Chennai Mathematical Institute


11:45; Lecture Hall 5
MSc Thesis Viva
Exponential bounds for the determinantal complexity of the permanent - an approach by Landsberg and Ressayre

Arpan Pal
Chennai Mathematical Institute.


Valiant's conjecture states that the permanent polynomial of an m x m matrix cannot be written as the determinant of an n x n matrix whose entries are affine linear functions in the m^2 entries of the permanent variables, unless n is exponential in m.

In this thesis we study recent work of Landsberg and Ressayre, wherein they prove this exponential bound when the resultant n x n matrix (whose determinant is the permanent) satisfies some natural symmetry conditions, satisfied for example by Grenet's construction. The proof of the exponential lower bound uses some non trivial ideas from algebraic groups and representation theory.