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. 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?
A question on GCT
cc.complexity theory
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 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.)