Cordian Riener: #P-hardness of matrix immanants on restricted matrices

Abstract

The determinant is a function from \(n\times n\) matrices one encounters in linear algebra. Permanents are less known and are obtained by neglecting the signum before each term of the determinant.  

The sharp difference of computational complexity of these two seemingly similar functions has been shown by Valiant in 1979. Immanants are matrix functions that generalise both determinants and permanents: They are obtained by replacing the signum with another character of the symmetric group. Immanents constitute therefore a family of matrix functions bridging from the determinant, which is obtained by the sign character and which can be evaluated in polynomial time to the #P hard permanent, which is obtained through the trivial character.  

The question, where on the way between the determinant and the permanent “easy” turns into “hard” has been initiated by Hartmann in the 1980 and improved by Barvinok and Bürgisser. Recently, Curticapean has completed this picture by providing a complete dichotomy result. In this talk we are going to examine what can be said if one restricts to the class of 0-1 matrices. In this context we show #P hardness for a large class of immanents. In particular, we characterise a class of partitions \(\lambda\) such that it is #P hard to compute the \(\lambda\)-immanent of adjacency matrices of edge-weighted, planar, directed graphs. 

This is joint work with Istvan Miklos.