5
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I saw the consequences section too $\endgroup$ – T.... Dec 20 '15 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.