<p>Even if deciding positivity of Kronecker coefficients is NP-hard, or even if there is no general positive formula for them, it is still quite possible for GCT to "work." Even under the preceding assumption, it is still possible that there is a positive formula (and even a polynomial-time decision procedure) for <em>some</em> of the rectangular Kronecker coefficients. If one could find such a formula, and then show that the corresponding irreducible representations appear with nonzero multiplicity in the coordinate ring of the orbit closure of an appropriately-sized permanent, it would still prove the (Strong) Permanent versus Determinant Conjecture.</p>

<p><strong>Update 8/30/15</strong>: I should add that, independent of positive combinatorial formulae, I think the geometric approach to complexity, as in GCT, is a <em>very</em> useful way to understand the structure of complexity classes, and using representation theory where it naturally arises (such as here) is always a Good Idea. Landsberg's work in this area is notable in this direction (i.e., using geometric techniques combined with representation theory, even in the absence of positive combinatorial formulae). <strong>[end update]</strong></p>

<p>[Now back to positive combinatorial formulae...] Even if more and more Kronecker coefficients end up being NP-hard to decide their vanishing, or if there isn't a positive combinatorial formula for them, (a) it is simply a testament to just how hard these problems are (after all, while GCT gets around the known barriers, it is still aiming at proving some very hard open problems), and/or (b) suggests where to narrow one's focus in order to get GCT to work (e.g., as above).</p>

<p>Also, although NP-hardness is "bad news" in general, it is not necessarily the end of the road. For example, although Hamiltonian Cycle is NP-hard, there are still lots of theorems and theoretical understanding around Hamiltonian cycles. The NP-hardness just leads one (or at least, me) to expect that there won't ever be a "complete theory of Hamiltonian cycles". But one doesn't need such a "complete theory of Kronecker coefficients" to prove a lower bound via GCT - one just needs one family of representations that vanishes on the orbit closure of the determinant but not on the orbit closure of the permanent.</p>

<p>(This answer also applies to the recent paper of <a href="http://arxiv.org/abs/1507.07131" rel="nofollow">Kahle and Michalek</a> which shows that there are families of plethysm multiplicities that are not given by the number of integer points in a natural family of polytopes.)</p>

CC BY-SA 3.0
2015-08-03T17:22:27.797Z
What happens if exactly the nature of rectangular Kronecker coefficients which GCT excatly needs to be $P$ turns out to be $NP$ hard? After all this is the $VNP$ vs $VP$ question here (things could infact be circular and ugly).
Turbo
CC BY-SA 3.0
2015-08-03T17:30:44.977Z
Even if it turns out that for every family of irreps that appears with nonzero multiplicity in the coordinate ring of the orbit closure of the permanent, the corresponding Kronecker decision problem is NP-hard, (a) there could still be a pos. combin. formula, and (b) the third paragraph of my answer still applies. The other thing is: if we knew this fact, we'd likely know so much more about the irreps on the orbit closure of perm than we currently do that we'd probably be able to resolve perm v det anyways.... PS - Email me.
Joshua Grochow
CC BY-SA 3.0
2015-08-03T17:32:41.383Z
what if there is no positive combinatorial formula at all?
Turbo
CC BY-SA 3.0
2015-08-03T17:47:50.473Z
If there is no positive combinatorial formula for Kronecker (or the multiplicities in the orbit closure of det) for any of the irreps appearing in the orbit closure of perm, that *still* doesn't rule out GCT. It just means that one will have to prove something about these multiplicities some other way, e.g. geometrically.
Joshua Grochow
CC BY-SA 3.0
2015-08-03T17:53:34.507Z
the thing is in one of his videos, he talks about a hidden Riemann Hypothesis for proving his positivity conjecture. AFAIK every riemann hypothesis comes along with a functional equation encoding some objects of interest. That seems unlikely because there is really no functional equation he is setting up?
Turbo
CC BY-SA 3.0
2015-08-03T17:55:41.760Z
Can you point me to the video and timestamp, so I can get better context?
Joshua Grochow
CC BY-SA 3.0
2015-08-03T17:58:04.327Z
This is video https://www.youtube.com/watch?v=WBjFRGOdeH8 trying to find ts.
Turbo
CC BY-SA 3.0
2015-08-03T18:16:42.320Z
Last minute of talk.
Turbo
CC BY-SA 3.0
2015-08-03T18:45:18.643Z
The rough idea is that there should be some kind of analogue of the Riemann Hypothesis over finite fields (aka Weil Conjectures), but related to the nonstandard quantum groups (as in GCT IV/VII/VIII). As far as I know, even coming up with the *statement* of what this analogue should be is still open...
Joshua Grochow
CC BY-SA 3.0
2015-08-03T19:04:11.910Z
over Finite fields, riemann hyp comes from associating a zeta function to a geometric object (namely the algebraic variety). What sort of geometric objects does GCT bring up? Moreover etale cohomology is used to prove RH over FF and every cohomology theory is conjectured to be from a Motivic cohomology in AG. So is there a connection to motives?
Turbo
CC BY-SA 3.0
2015-08-04T04:33:19.450Z
Turbo: Email me and I'm happy to discuss further, but this seems to have drifted from the question... (and is about such hypothetical objects/theories that I'm not sure how to even make a significantly more concrete question out of it...)
Joshua Grochow
CC BY-SA 3.0
2015-08-05T08:54:13.740Z
Do you know the works where positivity hypothesis is proved in relation to standard quantum groups that connects to standard riemann hypothesis over FF?
Turbo
CC BY-SA 3.0
2015-08-05T23:27:55.613Z
@Turbo: See the references in GCT VI (http://arxiv.org/abs/0704.0229); several of these are even given in the abstract there.
Joshua Grochow
CC BY-SA 3.0
2015-08-03T17:18:05.497Z
2015-08-30T23:58:07.490Z
2015-08-30T23:58:07.490Z
Joshua Grochow
<p>In paper 'On vanishing of Kronecker coefficients' here in <a href="http://arxiv.org/pdf/1507.02955v1.pdf">http://arxiv.org/pdf/1507.02955v1.pdf</a>, it is showed that deciding positivity of kronecker coefficients is in general NP hard. However there is a caveat which states that only positivity of 'rectangular Kronecker coefficients' is needed in <a href="https://en.wikipedia.org/wiki/Geometric_complexity_theory">GCT</a>. What is the implication to GCT if this also turns to be NP hard? </p>

<p>A related question is what is consequence to GCT if there is no general positive formula akin to one for special case of LR coefficients?</p>

<cc.complexity-theory>
A question on GCT
Turbo
# A question on GCT

(Asked by: username_0 on 2015-08-03)

In paper 'On vanishing of Kronecker coefficients' here in <http://arxiv.org/pdf/1507.02955v1.pdf>, it is showed that deciding positivity of kronecker coefficients is in general NP hard. However there is a caveat which states that only positivity of 'rectangular Kronecker coefficients' is needed in [GCT](https://en.wikipedia.org/wiki/Geometric_complexity_theory). What is the implication to GCT if this also turns to be NP hard?

A related question is what is consequence to GCT if there is no general positive formula akin to one for special case of LR coefficients?

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2015-08-03. Score: 10 | Accepted answer

Even if deciding positivity of Kronecker coefficients is NP-hard, or even if there is no general positive formula for them, it is still quite possible for GCT to "work." Even under the preceding assumption, it is still possible that there is a positive formula (and even a polynomial-time decision procedure) for *some* of the rectangular Kronecker coefficients. If one could find such a formula, and then show that the corresponding irreducible representations appear with nonzero multiplicity in the coordinate ring of the orbit closure of an appropriately-sized permanent, it would still prove the (Strong) Permanent versus Determinant Conjecture.

**Update 8/30/15**: I should add that, independent of positive combinatorial formulae, I think the geometric approach to complexity, as in GCT, is a *very* useful way to understand the structure of complexity classes, and using representation theory where it naturally arises (such as here) is always a Good Idea. Landsberg's work in this area is notable in this direction (i.e., using geometric techniques combined with representation theory, even in the absence of positive combinatorial formulae). **[end update]**

[Now back to positive combinatorial formulae...] Even if more and more Kronecker coefficients end up being NP-hard to decide their vanishing, or if there isn't a positive combinatorial formula for them, (a) it is simply a testament to just how hard these problems are (after all, while GCT gets around the known barriers, it is still aiming at proving some very hard open problems), and/or (b) suggests where to narrow one's focus in order to get GCT to work (e.g., as above).

Also, although NP-hardness is "bad news" in general, it is not necessarily the end of the road. For example, although Hamiltonian Cycle is NP-hard, there are still lots of theorems and theoretical understanding around Hamiltonian cycles. The NP-hardness just leads one (or at least, me) to expect that there won't ever be a "complete theory of Hamiltonian cycles". But one doesn't need such a "complete theory of Kronecker coefficients" to prove a lower bound via GCT - one just needs one family of representations that vanishes on the orbit closure of the determinant but not on the orbit closure of the permanent.

(This answer also applies to the recent paper of [Kahle and Michalek](http://arxiv.org/abs/1507.07131) which shows that there are families of plethysm multiplicities that are not given by the number of integer points in a natural family of polytopes.)

> **Comments:**
> **username_0**: What happens if exactly the nature of rectangular Kronecker coefficients which GCT excatly needs to be $P$ turns out to be $NP$ hard? After all this is the $VNP$ vs $VP$ question here (things could infact be circular and ugly).  
> **username_1**: Even if it turns out that for every family of irreps that appears with nonzero multiplicity in the coordinate ring of the orbit closure of the permanent, the corresponding Kronecker decision problem is NP-hard, (a) there could still be a pos. combin. formula, and (b) the third paragraph of my answer still applies. The other thing is: if we knew this fact, we'd likely know so much more about the irreps on the orbit closure of perm than we currently do that we'd probably be able to resolve perm v det anyways.... PS - Email me.  
> **username_0**: what if there is no positive combinatorial formula at all?  
> **username_1**: If there is no positive combinatorial formula for Kronecker (or the multiplicities in the orbit closure of det) for any of the irreps appearing in the orbit closure of perm, that *still* doesn't rule out GCT. It just means that one will have to prove something about these multiplicities some other way, e.g. geometrically.  
> **username_0**: the thing is in one of his videos, he talks about a hidden Riemann Hypothesis for proving his positivity conjecture. AFAIK every riemann hypothesis comes along with a functional equation encoding some objects of interest. That seems unlikely because there is really no functional equation he is setting up?  
> **username_1**: Can you point me to the video and timestamp, so I can get better context?  
> **username_0**: This is video https://www.youtube.com/watch?v=WBjFRGOdeH8 trying to find ts.  
> **username_0**: Last minute of talk.  
> **username_1**: The rough idea is that there should be some kind of analogue of the Riemann Hypothesis over finite fields (aka Weil Conjectures), but related to the nonstandard quantum groups (as in GCT IV/VII/VIII). As far as I know, even coming up with the *statement* of what this analogue should be is still open...  
> **username_0**: over Finite fields, riemann hyp comes from associating a zeta function to a geometric object (namely the algebraic variety). What sort of geometric objects does GCT bring up? Moreover etale cohomology is used to prove RH over FF and every cohomology theory is conjectured to be from a Motivic cohomology in AG. So is there a connection to motives?  
> **username_1**: Turbo: Email me and I'm happy to discuss further, but this seems to have drifted from the question... (and is about such hypothetical objects/theories that I'm not sure how to even make a significantly more concrete question out of it...)  
> **username_0**: Do you know the works where positivity hypothesis is proved in relation to standard quantum groups that connects to standard riemann hypothesis over FF?  
> **username_1**: @Turbo: See the references in GCT VI (http://arxiv.org/abs/0704.0229); several of these are even given in the abstract there.  

---

