GCT multiplicity-obstruction conjecture of Mulmuley and Sohoni
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.