GCT multiplicity-obstruction conjecture of Mulmuley and Sohoni

About 3 years old · traced to

Let dc(perm)\mathrm{dc}(\mathrm{per}_m) be the determinantal complexity of the m×mm\times m permanent. For integers d,n,md,n,m, let γλ,d,n,m\gamma_{\lambda,d,n,m} and δλ,d,n\delta_{\lambda,d,n} denote the multiplicities of the irreducible representation indexed by λ\lambda in the coordinate rings of the padded-permanent and determinant orbit closures, respectively. GCT multiplicity-obstruction conjecture. There exist multiplicity obstructions showing that

dc(perm)>mc\mathrm{dc}(\mathrm{per}_m)>m^c

for every constant cc; namely, for every n=O(mc)n=O(m^c) there exists an integer dd and a partition λ⊢dn\lambda\vdash dn such that

γλ,d,n,m>δλ,d,n.\gamma_{\lambda,d,n,m}>\delta_{\lambda,d,n}.

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

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.