Séminaire Lotharingien de Combinatoire, B75a (2016), 19 pp.
Peter Bürgisser
Permanent Versus Determinant, Obstructions, and Kronecker
Coefficients
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.
Received: November 25, 2015.
Accepted: April 24, 2016.
Final Version: May 9, 2016.
The following versions are available: