Hardness conjecture for immanants of large-depth Young diagrams

From papers

Let λ(n)\lambda(n) be any family of Young diagrams, where the depth of λ(n)\lambda(n) is the number of rows in the diagram. Assume that, for some constant δ>0\delta>0, the depth is nnδn-n^\delta. Immanant hardness conjecture. Then Immλ(n)\mathrm{Imm}_{\lambda(n)} is #P\#\mathrm{P}-hard. Equivalently, this concerns any family with a polynomial number of boxes to the right of the first column. The conjecture extends the paper's established hardness results for immanants associated with Young diagrams of bounded width, and its status is open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Stephan Mertens and Cristopher Moore, “The complexity of the fermionant, and immanants of constant width”, arXiv:1110.1821 (2011).

Solutions 0

No solutions have been posted yet.