<p>It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit <em>closure</em> of the determinant, and not merely use those on the orbit of the determinant as an upper bound. In using (a), one might at least still hope for a significant difference in the <em>magnitude</em> of the multiplicities, rather than small differences in their exact values - this should make such differences easier to detect.</p>

<p>The possibilities to use both (a) and (b) have been known for several years, though perhaps not everyone agreed regarding their necessity. (I personally have always thought that at the very least we'd need to do (b); it is very nice that their paper actually proves this.)</p>

<p>(Both (a) and (b) are clearly spelled out in Section 5 of the paper, entitled "Consequences for geometric complexity theory." Although my answer duplicates the points from the paper, I am posting it here both to give what I think is needed for a complete answer, and to assert that I agree with the authors that these are the ways forward.)</p>

CC BY-SA 3.0
2015-12-20T07:54:03.047Z
I saw the consequences section too
Turbo
CC BY-SA 3.0
2015-12-20T05:26:11.733Z
2015-12-20T05:26:11.733Z
Joshua Grochow
<p>A paper was posted in arxiv <a href="http://arxiv.org/pdf/1512.03798.pdf">http://arxiv.org/pdf/1512.03798.pdf</a> titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with first line in abstract stating 'We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial'.</p>

<p>If correct what is the implication of this result to the geometric complexity theory program for separating permanent from determinant?</p>

<lower-bounds><big-picture><algebraic-complexity><permanent><determinant>
Implications of a recent negative result to geometric complexity
Turbo
# Implications of a recent negative result to geometric complexity

(Asked by: username_0 on 2015-12-19)

A paper was posted in arxiv <http://arxiv.org/pdf/1512.03798.pdf> titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with first line in abstract stating 'We prove that in the geometric complexity theory program the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial determinantal complexity lower bounds for the permanent polynomial'.

If correct what is the implication of this result to the geometric complexity theory program for separating permanent from determinant?

**Tags:** lower-bounds, big-picture, algebraic-complexity, permanent, determinant

---

## 1 answers

### Answer by username_1 on 2015-12-20. Score: 8 | Accepted answer

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit *closure* of the determinant, and not merely use those on the orbit of the determinant as an upper bound. In using (a), one might at least still hope for a significant difference in the *magnitude* of the multiplicities, rather than small differences in their exact values - this should make such differences easier to detect.

The possibilities to use both (a) and (b) have been known for several years, though perhaps not everyone agreed regarding their necessity. (I personally have always thought that at the very least we'd need to do (b); it is very nice that their paper actually proves this.)

(Both (a) and (b) are clearly spelled out in Section 5 of the paper, entitled "Consequences for geometric complexity theory." Although my answer duplicates the points from the paper, I am posting it here both to give what I think is needed for a complete answer, and to assert that I agree with the authors that these are the ways forward.)

> **Comments:**
> **username_0**: I saw the consequences section too  

---

