Hardness conjecture for immanants of large-depth Young diagrams
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.
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
Sign in to submit a solution.
No solutions have been posted yet.