Leírás
Abstract:
Let $\lambda$ be a partition of $n$. Then the $\lambda$-immanant of an $n\times n$ matrix $A$ is defined as
$$
Im_{\lambda}(A) := \sum_{\rho \in S_n} \chi_{\lambda}(\rho) \prod_{i=1}^n a_{i,\rho(i)}
$$
where $S_n$ is the symmetric group on $n$ elements and $\chi_{\lambda}$ is the irreducible character of $S_n$ corresponding to the partition $\lambda$. Two well-known immanants are the determinant and the permanent, where $\chi$ 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^{\varepsilon}$ 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
The zoom link is
https://zoom.us/j/2961946869