Miklós István: Domino tilings, perfect matchings and hardness of computing immanants on restricted matrix classes (in Hungarian)

Let λ be a partition of n. Then the λ-immanant of an n×n matrix A is defined as

where Sn is the symmetric group on n elements and χλ is the irreducible character of Sn corresponding to the partition λ. Two well-known immanants are the determinant and the permanent, where χ are the sign and the trivial characters. Peter Bürgisser conjectured that most of the immanats are hard to compute. Recently Radu Curticapean proved a complete complexity dichotomy for immanants: under standard complexity assumptions, only immanants that are constant far from the determinant can be computed in polynomial time and all immanants which are nε far from the determinant are \#P-hard to compute.

In this talk we show that computing immanants for several partitions remains hard even when the computational problem is restricted on special matrices: on 0-1 matrices and on adjacency matrices of weighted planar directed graphs. These computations are related to computing matchings in planar graphs and perfect matchings in 3-regular graphs. The proofs need some interesting combinatorial lemmas on domino tilings.

Joint work with Cordian Riener, UiT, Norway.

References:

Curticapean, R. (2021)  A full complexity dichotomy for immanant families, https://arxiv.org/pdf/2102.04340.pdf, to appear at STOC'21

Miklós, I., Riener, C. (2021)  #P-hardness proofs of matrix immanants evaluated on restricted matrices, https://arxiv.org/pdf/2103.04934.pdf