GCT multiplicity-obstruction conjecture of Mulmuley and Sohoni
Let be the determinantal complexity of the permanent. For integers , let and denote the multiplicities of the irreducible representation indexed by in the coordinate rings of the padded-permanent and determinant orbit closures, respectively. GCT multiplicity-obstruction conjecture. There exist multiplicity obstructions showing that
for every constant ; namely, for every there exists an integer and a partition such that
Such an obstruction would rule out containment of the padded-permanent orbit closure in the determinant orbit closure and yield lower bounds for the permanent. The source gives no resolution.
References
Primary source
Greta Panova, “Computational Complexity in Algebraic Combinatorics”, arXiv:2306.17511 (2023).
Progress summary
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.