The computational complexity of plethysm coefficients

DOI10.1007/S00037-020-00198-4MaRDI QIDQ2027205zbMATH OpenOpenAlexFDO

Authors Nick Fischer, Christian Ikenmeyer

Publication date 25 May 2021

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.00788

zbMATH Keywords

computational complexitygeometric complexity theoryNP-hardnessplethysm coefficients

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: In two papers, B"urgisser and Ikenmeyer (STOC 2011, STOC 2013) used an adaption of the geometric complexity theory (GCT) approach by Mulmuley and Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of the matrix multiplication tensor. A key ingredient was information about certain Kronecker coefficients. While tensors are an interesting test bed for GCT ideas, the far-away goal is the separation of algebraic complexity classes. The role of the Kronecker coefficients in that setting is taken by the so-called plethysm coefficients: These are the multiplicities in the coordinate rings of spaces of polynomials. Even though several hardness results for Kronecker coefficients are known, there are almost no results about the complexity of computing the plethysm coefficients or even deciding their positivity. In this paper we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time. Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which we consider to be of independent interest. Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new equalities between certain plethysm coefficients and Kronecker coefficients.

Recommendations

• The complexity of computing Kronecker coefficients
• On vanishing of Kronecker coefficients
• On the complexity of computing Kronecker coefficients
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient

Cited in

(11)

• Equations for GL invariant families of polynomials
• Membership in moment polytopes is in NP and coNP
• Partial symmetries of iterated plethysms
• Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients
• The partition algebra and the plethysm coefficients. II: Ramified plethysm
• Deterministically approximating the volume of a Kostka polytope
• Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
• Some properties of the generalized Foulkes module
• The Newton polytope of the Kronecker product
• Asymptotics of plethysm
• Signed combinatorial interpretations in algebraic combinatorics

This page was built for publication: The computational complexity of plethysm coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2027205)