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

Description of video

Date: 5/6/21
Speaker :Miklós István


    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.


    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