Mulmuley's efficient generators conjecture for invariant rings

Let W=(W1,W2,)W=(W_1,W_2,\ldots) be a sequence of representations, with WiW_i an SLni\operatorname{SL}_{n_i}-representation of dimension NiN_i. An arithmetic circuit succinctly encodes the generators of the invariant ring of an SLni\operatorname{SL}_{n_i}-representation WiW_i if, after assigning arbitrary complex values to its auxiliary variables, the resulting polynomials are invariants generating C[Wi]SLni\mathbb C[W_i]^{\operatorname{SL}_{n_i}} as a ring. Then there exists a polynomial pp and a sequence CiC_i of arithmetic circuits of size p(niNi)\leq p(n_iN_i) such that CiC_i succinctly encodes the generators of the invariant ring of WiW_i. This conjecture asks for uniformly efficient descriptions of generators for invariant rings, a problem motivated by computational complexity and geometric complexity theory. The source states that the original conjecture for SLn\operatorname{SL}_n remained open, and that Oliveira stated its resolution as an open problem in December 2019.

Sources & referencesView supporting material

Primary source

Christian Ikenmeyer and Michael Walter, “Hyperpfaffians and Geometric Complexity Theory”, arXiv:1912.09389 (2020).

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.