On the complexity of computing Kronecker coefficients

DOI10.1007/S00037-015-0109-4MaRDI QIDQ2012174zbMATH OpenOpenAlexFDO

Authors Igor Pak, Greta Panova

Publication date 28 July 2017

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Kronecker coefficientssymmetric group representationsGCT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symmetric functions and generalizations (05E05) Combinatorial aspects of partitions of integers (05A17) Representations of finite symmetric groups (20C30)

Abstract: We study the complexity of computing Kronecker coefficients $g(lambda,mu,u)$. We give explicit bounds in terms of the number of parts $ell$ in the partitions, their largest part size $N$ and the smallest second part $M$ of the three partitions. When $M=O(1)$, i.e. one of the partitions is hook-like, the bounds are linear in $logN$, but depend exponentially on $ell$. Moreover, similar bounds hold even when $M=e^{O(ell)}$. By a separate argument, we show that the positivity of Kronecker coefficients can be decided in $O(logN)$ time for a bounded number $ell$ of parts and without restriction on $M$. Related problems of computing Kronecker coefficients when one partition is a hook, and computing characters of $S_n$ are also considered.

Recommendations

• The complexity of computing Kronecker coefficients
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• On the complexity of computing determinants
• On the growth of Kronecker coefficients
• Computation of dilated Kronecker coefficients
• Krylov complexity and orthogonal polynomials
• scientific article; zbMATH DE number 2151192
• On Kronecker polynomials
• On the asymptotics of Kronecker coefficients.
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 3115125 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3681986 (Why is no real title available?)
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• scientific article; zbMATH DE number 1405499 (Why is no real title available?)
• A combinatorial interpretation for the coefficients in the Kronecker product \(s_{(n-p,p)} \ast s_\lambda\)
• A formula for the Kronecker products of Schur functions of hook shapes
• An invitation to the generalized saturation conjecture
• Applications of approximation algorithms to cooperative games
• Combinatorics and geometry of Littlewood-Richardson cones
• Deciding positivity of Littlewood-Richardson coefficients
• Effective lattice point counting in rational convex polytopes
• Fast integer programming in fixed dimension
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Integer points in polyhedra
• Kronecker coefficients for one hook shape
• Kronecker multiplicities in the \((k,\ell)\) hook are polynomially bounded.
• Kronecker products, characters, partitions, and the tensor square conjectures
• Nonzero Kronecker coefficients and what they tell us about spectra
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• On rectangular Kronecker coefficients.
• On the Computation of Clebsch–Gordan Coefficients and the Dilation Effect
• On the Kronecker product of S_n characters
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• On the complexity of computing Kronecker coefficients
• Products and Plethysms of Characters with Orthogonal, Symplectic and Symmetric Groups
• Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
• Reductions of Young tableau bijections
• Stability of Kronecker products of irreducible characters of the symmetric group
• Stable properties of plethysm: On two conjectures of Foulkes
• Tableau switching: Algorithms and applications
• Tensorprodukte von Charakteren der symmetrischen Gruppe
• The Analysis of the Direct Product of Irreducible Representations of the Symmetric Groups
• The Complexity of Three-Way Statistical Tables
• The Kronecker Product of Symmetric Group Representations
• The Kronecker product of Schur functions indexed by two-row shapes or hook shapes
• The complexity of computing Kronecker coefficients
• The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
• The partition algebra and the Kronecker coefficients.
• The stability of the Kronecker product of Schur functions
• Unimodality via Kronecker products

Cited in

(32)

• Plane partitions and the combinatorics of some families of reduced Kronecker coefficients
• The complexity of computing Kronecker coefficients
• On the complexity of computing Kronecker coefficients
• Cluster algebras, invariant theory, and Kronecker coefficients. II.
• Saxl conjecture for triple hooks
• Effective Poset Inequalities
• Membership in moment polytopes is in NP and coNP
• Quantum mechanics of bipartite ribbon graphs: integrality, lattices and Kronecker coefficients
• The computational complexity of plethysm coefficients
• On the Complexity of Hybrid $n$ -Term Karatsuba Multiplier for Trinomials
• Bounds on Kronecker coefficients via contingency tables
• Critical classes, Kronecker products of spin characters, and the Saxl conjecture
• Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients
• Kronecker coefficients via symmetric functions and constant term identities
• Algorithmically distinguishing irreducible characters of the symmetric group
• On the Kronecker product of Schur functions of square shapes
• Non-invertible symmetries in \(S_N\) orbifold CFTs and holography
• All Kronecker coefficients are reduced Kronecker coefficients
• Vanishing of Littlewood-Richardson polynomials is in P
• Estimating and computing Kronecker coefficients: a vector partition function approach
• Tensor product Markov chains
• Breaking down the reduced Kronecker coefficients
• Vector partition functions and Kronecker coefficients
• Interview with Victor Reiner
• Combinatoric topological string theories and group theory algorithms
• Interview with Igor Pak
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• Algorithm for computing Kronecker basis
• A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
• Invariant operators, orthogonal bases and correlators in general tensor models
• Computation of dilated Kronecker coefficients
• Kostka multiplicity one for multipartitions

Describes a project that uses

Uses Software

• LattE

This page was built for publication: On the complexity of computing Kronecker coefficients

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