Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2103.04934 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915627474616320 |
|---|---|
| author | Miklos, Istvan Riener, Cordian |
| author_facet | Miklos, Istvan Riener, Cordian |
| contents | We establish the $\#P$-hardness of computing a broad class of immanants, even when restricted to specific categories of matrices. Concretely, we prove that computing $λ$-immanants of $0$-$1$ matrices is $\#P$-hard whenever the partition~$λ$ contains a sufficiently large domino-tileable region, subject to certain technical conditions.
We also give hardness proofs for some $λ$-immanants of weighted adjacency matrices of planar directed graphs, such that the shape $λ= (\mathbf{1} + λ_d)$ has size $n$ such that $|λ_d| = n^\varepsilon$ for some $0 < \varepsilon < \frac{1}{2}$, and such that for some $w$, the shape $λ_d/(w)$ is tileable with $1 \times 2$ dominos. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_04934 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | #P-hardness proofs of matrix immanants evaluated on restricted matrices Miklos, Istvan Riener, Cordian Computational Complexity Representation Theory We establish the $\#P$-hardness of computing a broad class of immanants, even when restricted to specific categories of matrices. Concretely, we prove that computing $λ$-immanants of $0$-$1$ matrices is $\#P$-hard whenever the partition~$λ$ contains a sufficiently large domino-tileable region, subject to certain technical conditions. We also give hardness proofs for some $λ$-immanants of weighted adjacency matrices of planar directed graphs, such that the shape $λ= (\mathbf{1} + λ_d)$ has size $n$ such that $|λ_d| = n^\varepsilon$ for some $0 < \varepsilon < \frac{1}{2}$, and such that for some $w$, the shape $λ_d/(w)$ is tileable with $1 \times 2$ dominos. |
| title | #P-hardness proofs of matrix immanants evaluated on restricted matrices |
| topic | Computational Complexity Representation Theory |
| url | https://arxiv.org/abs/2103.04934 |