GCT multiplicity-obstruction conjecture of Mulmuley and Sohoni

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.

Sources & referencesView supporting material

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.