Hardness conjecture for immanants of large-depth Young diagrams

At least 14 years old · documented by

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 n−nδ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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.