Permanent versus determinant, obstructions, and Kronecker coefficients
arXiv:1511.08113
Abstract
We give an introduction to some of the recent ideas that go under the name "geometric complexity theory". We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.
arXiv commentSurvey, 17 pages, 1 figure
References in corpus (10)
- Quantum marginal problem and representations of the symmetric group
- On vanishing of Kronecker coefficients
- Nonvanishing of Kronecker coefficients for rectangular shapes
- Even Partitions in Plethysms
- Kronecker coefficients for one hook shape
- Inequalities for Moment Cones of Finite-Dimensional Representations
- Membership in moment polytopes is in NP and coNP
- Permanent versus determinant: not via saturations
- The boundary of the orbit of the 3 by 3 determinant polynomial
- Binary Determinantal Complexity