Mulmuley's efficient generators conjecture for invariant rings

About 7 years old · traced to

Let W=(W1,W2,…)W=(W_1,W_2,\ldots) be a sequence of representations, with WiW_i an SL⁡ni\operatorname{SL}_{n_i}-representation of dimension NiN_i. An arithmetic circuit succinctly encodes the generators of the invariant ring of an SL⁡ni\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]SL⁡ni\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 SL⁡n\operatorname{SL}_n remained open, and that Oliveira stated its resolution as an open problem in December 2019.

References

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.