Rectangular Kronecker coefficients and plethysms in geometric complexity theory

作者: Christian Ikenmeyer , Greta Panova

DOI: 10.1016/J.AIM.2017.08.024

关键词:

摘要: Abstract We prove that in the geometric complexity theory program vanishing of rectangular Kronecker coefficients cannot be used to superpolynomial determinantal lower bounds for permanent polynomial. Moreover, we positivity a large class partitions where side lengths rectangle are at least quadratic length partition. also compare with their corresponding plethysm coefficients, which leads new bound coefficients. saturation semigroup is trivial, show stretching factor 2 long first row, and completely classify limit were introduced by Manivel 2011.

参考文章(46)
Jesko Hüttenhain, Christian Ikenmeyer, Binary determinantal complexity Linear Algebra and its Applications. ,vol. 504, pp. 559- 573 ,(2016) , 10.1016/J.LAA.2016.04.027
Akihiro Yabe, Bi-polynomial rank and determinantal complexity. arXiv: Computational Complexity. ,(2015)
Mercedes H. Rosas, The Kronecker Product of Schur Functions Indexed by Two-Row Shapes or Hook Shapes Journal of Algebraic Combinatorics. ,vol. 14, pp. 153- 173 ,(2001) , 10.1023/A:1011942029902
Jerzy Weyman, J. M. Landsberg, Peter Bürgisser, Laurent Manivel, An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP arXiv: Computational Complexity. ,(2009)
Christian Ikenmeyer, The Saxl conjecture and the dominance order Discrete Mathematics. ,vol. 338, pp. 1970- 1975 ,(2015) , 10.1016/J.DISC.2015.04.027
Ricky Ini Liu, A simplified Kronecker rule for one hook shape arXiv: Combinatorics. ,(2014)
Seinosuke Toda, Classes of Arithmetic Circuits Capturing the Complexity of Computing the Determinant IEICE Transactions on Information and Systems. ,vol. 75, pp. 116- 124 ,(1992)
Christian Ikenmeyer, Ketan D. Mulmuley, Michael Walter, On vanishing of Kronecker coefficients arXiv: Computational Complexity. ,(2015) , 10.1007/S00037-017-0158-Y
J. M. Landsberg, Geometric complexity theory: an introduction for geometers Annali Dell'universita' Di Ferrara. ,vol. 61, pp. 65- 117 ,(2015) , 10.1007/S11565-014-0202-7
Jin-Yi Cai, Xi Chen, Dong Li, Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic Computational Complexity. ,vol. 19, pp. 37- 56 ,(2010) , 10.1007/S00037-009-0284-2