Combinatorics and Complexity of Kronecker Coefficients

on YouTube ↗59m

" summary

Defines Kronecker coefficients g(λ,μ,ν) as tensor-product multiplicities and states key complexity claims: positivity decision is conjectured polynomial but not even known to lie in NP, and exact computation is #P-hard (so in GapP). Main tools are symmetric‑function identities, a character lower bound comparing g to |χν|, reductions to counting three‑way contingency tables, and partition asymptotics; special cases become tractable (hooks, two rows, fixed length) and some stability/semigroup finite‑generation results give theoretical linear‑time tests but no practical generator list.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 2:17The combinatorial problem
3. 5:20Kronecker coefficients and GCT
4. 11:55Positivity problems
5. 14:40Positivity results : Saxl conjecture
6. 19:46Character lemma
7. 27:01Symmetric function techniques 11
8. 33:13Easy example MathOverflow question Jiarui Feil: Is there an easy way to see why
9. 36:04Applications: partitions inside a rectangle m
10. 39:59Kronecker and partitions inside a rectangle
11. 42:45Further: effective bounds
12. 44:18NP and #P from combinatorics
13. 45:57Complexity of KRON and KP
14. 50:16Proofs 1: the Reduction Lemma
15. 52:22Proofs II: Explicit bounds on KRON complexity
16. 53:51The theorem
17. 57:48The analogous question for characters