On the complexity of computing Kronecker coefficients

DOI10.1007/S00037-015-0109-4zbMATH Open1367.05012arXiv1404.0653OpenAlexW2962883077MaRDI QIDQ2012174FDOQ2012174

Igor Pak, Greta Panova

Publication date: 28 July 2017

Published in: Computational Complexity (Search for Journal in Brave)

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.

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)

Cites Work

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

Cited In (24)

• On the complexity of computing Kronecker coefficients
• Cluster algebras, invariant theory, and Kronecker coefficients. II.
• Effective Poset Inequalities
• Quantum mechanics of bipartite ribbon graphs: integrality, lattices and Kronecker coefficients
• Saxl conjecture for triple hooks
• On the Complexity of Hybrid $n$ -Term Karatsuba Multiplier for Trinomials
• Bounds on Kronecker coefficients via contingency tables
• Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients
• Critical classes, Kronecker products of spin characters, and the Saxl conjecture
• On the Kronecker product of Schur functions of square shapes
• Algorithmically distinguishing irreducible characters of the symmetric group
• Non-invertible symmetries in \(S_N\) orbifold CFTs and holography
• All Kronecker coefficients are reduced Kronecker coefficients
• Title not available (Why is that?)
• Vanishing of Littlewood-Richardson polynomials is in P
• Tensor product Markov chains
• Interview with Victor Reiner
• Vector partition functions and Kronecker coefficients
• Breaking down the reduced Kronecker coefficients
• Interview with Igor Pak
• Combinatoric topological string theories and group theory algorithms
• 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

Uses Software

• LattE

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the complexity of computing determinants 👍 👎
• On Kronecker polynomials 👍 👎
• On the growth of Kronecker coefficients 👍 👎
• On the asymptotics of Kronecker coefficients. 👍 👎
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients 👍 👎
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory 👍 👎
• Computation of dilated Kronecker coefficients 👍 👎
• Krylov complexity and orthogonal polynomials 👍 👎

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)