Hardness conjecture for immanants of large-depth Young diagrams
Let be any family of Young diagrams, where the depth of is the number of rows in the diagram. Assume that, for some constant , the depth is . Immanant hardness conjecture. Then is -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.