2021/03/08 by Miklos, Istvan, Riener, Cordian
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Representation Theory (math.RT)
paper · doi:10.48550/arxiv.2103.04934
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 λ= (1 + λd) has size n such that |λd| = nε for some 0 < ε < (1)/(2), and such that for some w, the shape λd/(w) is tileable with 1 × 2 dominos.