\begin{document}

\title{Permanent versus determinant, obstructions,\ and Kronecker
  coefficients$^*$}

\begin{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.
\epsilonnd{abstract}

\section{Motivation} 

The {\epsilonm determinant polynomial} is defined as 
$$
 \mathrm{det}_n := \mathrm{det}(X) := \sum_{\pi\in S_n} \mathrm{sgn}(\pi) \prod_{i=1}^n x_{i\pi(i)} ,
$$
where $x_{ij}$ are variables over a field $K$. 
The determinant derives its importance from the fact that it defines a 
group homomorphism $\mathrm{det}\colon \mathrm{GL}_n(K) \to K^\times$ due to 
$$
 \mathrm{det}(X\cdot Y) = \mathrm{det} (X)\, \mathrm{det}(Y) .
$$
It is highly relevant for computational mathematics that the determinant 
has an efficient computation. For instance, by using Gaussian
elimination, it can be computed with $O(n^3)$ arithmetic operations.

The definition of the {\epsilonm permanent polynomial} looks similarly as
for that of the determinant: 
$$
 \mathrm{per}_n := \mathrm{per}(X) := \sum_{\pi\in S_n} \prod_{i=1}^n x_{i\pi(i)} ,
$$
but without the sign changes. The permanent has less 
symmetries: 
$\mathrm{per}(X\cdot Y) = \mathrm{per}(X) \mathrm{per}(Y)$ holds 
if $X$ is a product of a permutation 
and a diagonal matrix, or if $Y$ is so; but in general, the 
multiplicativity property is violated. 
Also, for the permanent, there is no known efficient computation. 
We don't know whether there is a polynomial time algorithm for computing it. 
The permanent often shows up in algebraic combinatorics and statistical physics 
as a generating function in enumeration problems. 

In computer science, the permanent is known as a universal (or complete) problem 
in a class of weighted enumeration problems. One says that the family 
$(\mathrm{per}_n)$ of permanents is $\mathrm{VNP}$-complete. This theory was created in 1979
by L.~Valiant~\cite{Val:79b}. 
See \cite{buer:00-3,mapo:08} for more information.   

Proving that computing $\mathrm{per}_n$ requires superpolynomially many
arithmetic operations in~$n$ 
is considered the holy grail of algebraic complexity theory. This essentially amounts to proving 
the separation $\mathrm{VP}\ne\mathrm{VNP}$ of complexity classes. 
This separation is an ``easier'' variant of the famous P$\,\ne\,$NP problem. 

\section{Determinantal complexity}

Note that 
$\mathrm{per}\begin{bmatrix} a & b \\ c & d \epsilonnd{bmatrix} = \mathrm{det} \begin{bmatrix} a & -b \\ c & d \epsilonnd{bmatrix}$.  
P\'olya~\cite{polya:13} asked in 1913 whether such a formula is also
possible for $n\ge 3$, i.e., whether there is a sign matrix $[\epsilonpsilon_{ij}]$ 
such that $\mathrm{per}_n = \mathrm{det}[\epsilonpsilon_{ij} x_{ij}]$. 
This was disproved by Szeg{\H o}~\cite{szego:13} in the same year. 
Marcus and Minc~\cite{marcus-minc:61} strengthened this result by showing that there is no 
matrix $[f_{pq }]$ of linear forms $f_{pq}$ in the variables $x_{ij}$ such that 
$\mathrm{per}_n = \mathrm{det}[f_{pq}]$. 

But what happens if we allow for the determinant a larger matrix? 

We can express $\mathrm{per}_3$ as the determinant of a matrix of size 7, 
whose entries are constants or variables, cf.~\cite{grenet:11}: 
$$
 \mathrm{per}_3 = \mathrm{det}\begin{bmatrix} 
0&0&0&0&x_{33}&x_{32}&x_{31}\\
x_{11}&1&0&0&0&0&0\\
x_{12}&0&1&0&0&0&0\\
x_{13}&0&0&1&0&0&0\\
0&x_{22}&x_{21}&0&1&0&0\\
0&x_{23}&0&x_{21}&0&1&0\\
0&0&x_{23}&x_{22}&0&0&1
\epsilonnd{bmatrix}.
$$

\begin{definition}
The {\epsilonm determinantal complexity} $\mathrm{dc}(f)$ of a polynomial~$f\in K[x_1,\ldots,x_N]$ 
is the smallest~$s$ such that there exists a square matrix $A$ of size $s$, whose entries are affine 
linear functions of $x_1,\ldots,x_N$, such that $f= \mathrm{det}(A)$.  
Moreover, we write $\mathrm{dc}(m) := \mathrm{dc}(\mathrm{per}_m)$. 
\epsilonnd{definition}

We clearly have $\mathrm{dc}(2)=2$. 
By the above formula, $\mathrm{dc}(3)\le 7$. 
Recent work showed the optimality: $\mathrm{dc}(3)=7$; cf.\ 
\cite{hu-ik:14,al-bo-ve:15}.

\subsection{An upper bound}

The following nice upper bound is due to Grenet~\cite{grenet:11}, 
based on ideas in Valiant~\cite{Val:79b}. 

\begin{theorem}[Grenet]\lambdabel{th:grenet}
We have $\mathrm{dc}(m) \le 2^m -1$.  
\epsilonnd{theorem}

\begin{proof}
1. We first give the determinant of a matrix $A$ of size $m$ 
a combinatorial interpretation. 
We consider the complete directed graph with the node set 
$[m]:=\{1,2,\ldots m\}$ and the edges $(i,j)$ carrying the weight~$a_{ij}$. 
Moreover, we interpret a permutation $\pi$ of $[m]$ as the collection of 
their disjoint cycles (including loops for the fixed points) and call this 
a {\epsilonm cycle cover} $c$ of the digraph. We write $\mathrm{sgn}(c):=\mathrm{sgn}(\pi)$. 
The weight of $c$ is defined as 
the product of the weights of the edges occurring in $c$. 

Then we see that $\mathrm{det}(A)$ equals the sum of the signed weights 
over all cycle covers of the digraph: 
$$
 \mathrm{det}(A) = \sum_c \mathrm{sgn}(c) \mathrm{weight}(c) .
$$

2. We build now a digraph $P_m$ (see Figure~\ref{fig:jan}). 
Its node set is the power set $2^{[m]}$ of $[m]$.
For each $S\in 2^{[m]}$ of size $i-1$, where $1\le i \le m$,  
and $j\in [m]\setminus S$,  
we form a directed edge from $S$ to $S\cup\{j\}$ of weight $x_{ij}$. 
It is easy to see that 
$$
 \mathrm{per}_m(X) = \sum_\pi \mathrm{weight}(\pi) ,
$$
where the sum is over all directed paths $\pi$ going from
$\epsilonmptyset$ to $[m]$.
(We define the weight of $\pi$ as the product of the weights 
of its edges.)   

\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{kleines-bild.pdf}
\epsilonnd{center}
\caption{{\small The construction for $m=3$. Courtesy of J.~Draisma~\cite{draisma-siam:15}.}}\lambdabel{fig:jan}
\epsilonnd{figure}

We perform some modifications in this graph: we add loops 
of weight one at all nodes $S\in 2^{[m]}$ different from $\epsilonmptyset$ and $[m]$, 
and we identify the node $\epsilonmptyset$ with the node $[m]$. 
Let $A$ denote the weighted adjacency matrix of the resulting digraph. 
Its size is $2^m -1$. 

Then it is easy to see that we obtain a weight preserving bijection between the 
set of directed paths $\pi$ between $\epsilonmptyset$ and $[m]$ in the 
original digraph and the set of cycle covers $c_\pi$ in the modified digraph.
We obtain 
$$
 (-1)^{m-1} \mathrm{per}_m(X) = \sum_\pi (-1)^{m-1} \mathrm{weight}(\pi) = \sum_c \mathrm{sgn}(c) \mathrm{weight}(c) ,
$$
which shows that indeed $\mathrm{dc}(m) \le 2^m -1$. 
\epsilonnd{proof}

Landsberg and Ressayre~\cite{lare:15} recently proved that 
the representation $\mathrm{per}_m = \mathrm{det} (A)$ in the proof of
Theorem~\ref{th:grenet} is optimal among all representations 
respecting ``half of the symmetries'' of $\mathrm{per}_m$. 

\subsection{A lower bound}

The following result due to Mignon and Ressayre~\cite{mignon-ressayre:04} is the 
best known lower bound for $\mathrm{dc}(m)$, 
except for a recent improvement over $K=\mathbb{R}$ due 
to Yabe~\cite{yabe:15}, which states 
$(m-1)^2 +1 \le \mathrm{dc}(m)$. 

\begin{theorem}[Mignon and Ressayre]\lambdabel{th:mr}
We have $m^2/2 \le \mathrm{dc}(m)$ if ${\mathrm{char}} K= 0$. 
\epsilonnd{theorem}

\begin{proof}
The idea is to consider the {\epsilonm Hessian} $H_f$ of a polynomial 
$f\in K[x_1,\ldots,x_N]$:
$$
 H_f := \left[ \frac{\partial^2f}{\partial x_\alpha \partial x_\beta} \right]_{1\le\alpha,\beta\le N} .
$$
We note that 
$\frac{\partial^2\mathrm{det}_n}{\partial x_{ij} \partial x_{k\epsilonll}}$ 
equals the minor of $X$ obtained by deleting the rows $i,j$ and 
colums $j,\epsilonll$. 

The following is straightforward to verify using the chain rule.

\begin{lemma}\lambdabel{le:HT}
If we perform an affine linear transformation on 
$f\in K[x_1,\ldots,x_N]$, namely,
$$
 F(x_1,\ldots,x_M) := f\Big( L\cdot\begin{bmatrix}x_1\\ \vdots\\ x_M\epsilonnd{bmatrix} + b\Big),
 \quad L\in K^{N\times M}, b\in K^N ,
$$
then 
$$
  H_F(x) = L^T H_f(Lx + b) L .
$$
\epsilonnd{lemma}

Now we assume $\mathrm{dc}(m) \le n$. 
This means we have a representation
\begin{equation}\lambdabel{mr-uno}
 \mathrm{per}_m(X) = \mathrm{det}(A(X)) ,
\epsilonnd{equation}
where $A(X)$ is of size $n$ and the entries of $A$ are affine linear in the $X$-variables. 
Lemma~\ref{le:HT} implies 
\begin{equation}\lambdabel{mr-due}
 H_\mathrm{per}(X) = L^T H_\mathrm{det}(A(X)) L,
\epsilonnd{equation}
where $L \in K^{n^2\times m^2}$ is the matrix of the linear map
corresponding to the affine map $A$. 

We substitute in \epsilonqref{mr-uno} the matrix $X$ 
by some $M\in K^{m\times m}$ which satisfies $\mathrm{per}(M)=0$, 
and we set $N:= A(M)$. 
Then, 
$$
  0 = \mathrm{per} (M) = \mathrm{det}(A(M)) = \mathrm{det}(N),
$$
so that $N$ is rank deficient. 
Moreover, \epsilonqref{mr-due} implies 
\begin{equation}\lambdabel{eq:conclusion}
 \mathrm{rank} H_\mathrm{per}(M) \ \le\ \mathrm{rank} H_\mathrm{det} (N) .
\epsilonnd{equation}

The determinant is special in the sense that its 
Hessian has small rank at rank deficient matrices $N$. 

\begin{lemma}\lambdabel{le:H-rank-det}
The rank of $H_\mathrm{det}(N)$ at a matrix $N\in K^{n\times n}$ only depends on the 
rank $s$ of $N$. If $s<n$, then 
$$
 \mathrm{rank} H_\mathrm{det}(N) \ \le\ 2n .
$$
\epsilonnd{lemma}

\begin{proof}(Sketch)
$\mathrm{det}\colon K^{n\times n} \to K$ is an invariant with respect to the action
of $\mathrm{SL}_n\times\mathrm{SL}_n$ on $K^{n\times n}$ via 
$(S,T) \cdot N := SNT^{-1}$. Using Lemma~\ref{le:HT} one sees that 
$H_\mathrm{det}\colon K^{n\times n} \to K$ is an invariant under this action as well.
This implies the first assertion. 

For the second assertion, take $N$ in normal form 
($s$ ones on the diagonal and zeros otherwise) and compute the rank $H_\mathrm{det}(N)$. 
\epsilonnd{proof}

In contrast, the permanent has the following property.

\begin{lemma}\lambdabel{le:ex-M}
There exists $M\in K^{m\times m}$ such that $\mathrm{per}(M) = 0$ and 
$H_\mathrm{per}(M)$ has rank $m^2$. (Here we assume ${\mathrm{char}} K= 0$.) 
\epsilonnd{lemma}

\begin{proof}(Sketch)
One may take 
$$
 M=\begin{bmatrix}
1-m&1&\cdots&1\\
1&1&\cdots &1\\
\vdots&\vdots& & \vdots\\
1&1&\cdots &1
\epsilonnd{bmatrix},
$$
which satisfies $\mathrm{per}(M)=0$. 
It is elementary, though a bit cumbersome, to verify
that $H_\mathrm{per}(M)$ has full rank.
\epsilonnd{proof}

Using Lemma~\ref{le:H-rank-det} and Lemma~\ref{le:ex-M} in \epsilonqref{eq:conclusion}, 
we obtain 
$$
 m^2 = \mathrm{rank} H_\mathrm{per}(M) \ \le\ \mathrm{rank} H_\mathrm{det} (N) \le 2n
$$
and the assertion follows.
\epsilonnd{proof}

We remark that~\cite{cai:2010} has an extension of Theorem~\ref{th:mr} to positive characteristic. 

\section{An attempt via algebraic geometry and representation theory}
\lambdabel{se:attempt}

How could we possibly prove better lower bounds on $\mathrm{dc}(m)$? 

\subsection{The determinant variety $\Omega_n$}

We assume $K=\mathbb{C}$ in the following. 
We consider $\mathrm{Sym}^n\mathbb{C}^{n^2}$ as the space of homogeneous polynomials of degree~$n$ 
in $n^2$ variables. The group $\mathrm{GL}_{n^2}$ acts on $\mathrm{Sym}^n\mathbb{C}^{n^2}$ by linear substitution. 

\begin{definition}
The {\epsilonm orbit} $\mathrm{GL}_{n^2}\cdot \mathrm{det}_n$ is obtained by applying all possible 
invertible linear transformations to $\mathrm{det}_n$.  
The {\epsilonm orbit closure} of $\mathrm{det}_n$, 
$$
\Omega_n := \ol{\mathrm{GL}_{n^2}\cdot \mathrm{det}_n} \subseteq \mathrm{Sym}^n\mathbb{C}^{n^2}, 
$$ 
is its closure  with respect to the Euclidean topology. 
We call $\Omega_n$ the {\epsilonm determinant variety}. 
\epsilonnd{definition}

\begin{example}
1. If $n=2$, we have 
$$
\mathrm{GL}_{4}\cdot \mathrm{det}_2 = \{\mbox{quadratic forms of rank $4$}\}, \quad
   \Omega_2 := \mathrm{Sym}^2\mathbb{C}^{4} .
$$ 

2. We have for $\epsilon\to 0$
$$
 \mathrm{det}\begin{bmatrix} x_{11} & \epsilon x_{12} \\ \epsilon x_{21} & x_{22} \epsilonnd{bmatrix} 
 = x_{11} x_{22} - \epsilon^2 x_{12} x_{21} \longrightarrow x_{11} x_{22} \in \Omega_2 
  \quad\mbox{ for $\epsilon\to 0$.}
$$
The latter observation generalizes to any $n$ and hence $x_{11}\cdots x_{nn} \in \Omega_n$. 
\epsilonnd{example}

\begin{remark}
For $n=3$, the boundary of $\Omega_n$ has been determined recently~\cite{lahu:16}, 
but for $n=4$ it is already unknown. 
\epsilonnd{remark}

The following observation allows to study $\Omega_n$ 
with the methods of algebraic geometry. 

\begin{theorem}\lambdabel{th:tops}
$\Omega_n$ is Zariski-closed, i.e., the zero set of a system of polynomial equations.
\epsilonnd{theorem}

This is a consequence of a general principle saying that for 
any constructible subset of $\mathbb{C}^N$, the Zariski closure and the closure 
with respect to the Euclidean topology coincide, see Mumford~\cite[\S2.C]{mumf:95}. 

We make now the following observation. 

Suppose $\mathrm{dc}(m) \le n$ with $m>2$, say 
$\mathrm{per}_m(X) = \mathrm{det} (A(X))$, where $A(X)$ is of size~$n$, with affine linear entries 
in $x_{11},\ldots,x_{mm}$. 
(By Theorem~\ref{th:mr} we have $m<n$.)  
Homogenizing this equation with the additional variable $t$, 
we obtain
\begin{equation}\lambdabel{eq:perder}
t^{n-m} \mathrm{per}_m(X) = t^n \mathrm{per}_m\Big(\frac{1}{t}X\Big) =  t^n \mathrm{det}\Big(A\Big(\frac{1}{t}X\Big)\Big) 
   =  \mathrm{det}\Big(t A\Big(\frac{1}{t}X\Big)\Big) . 
\epsilonnd{equation}
The entries of the matrix $t A(\frac{1}{t}X)$ 
are linear forms in $t$ and the $X$-variables.
We call $t^{n-m} \mathrm{per}_m(X)$ the {\epsilonm padded permanent}. 

The $n^2$ entries of $t A(\frac{1}{t}X)$,  arranged as a vector, 
may be thought of as being obtained by multiplying 
some matrix $L \in \mathbb{C}^{n^2 \times (m^2 +1)}$ with $(x_{11},\ldots,x_{mm},t)^T$. 
Now think of $t$ as being one of the variables in 
$\{x_{11},\ldots,x_{nn}\} \setminus \{x_{11},\ldots,x_{mm}\}$.
Then 
$L\cdot (x_{11},\ldots,x_{mm},t)^T = L' \cdot (x_{11},\ldots,x_{nn})^T$, 
where $L'$ is obtained by appending $n^2-m^2-1$ zero columns to $L$. 
We thus see that $t^{n-m} \mathrm{per}_m(X)$ is obtained from $\mathrm{det}_n$ by the 
substitution $L'$. Since $\mathrm{GL}_{n^2}$ is dense in $\mathbb{C}^{n\times n}$, 
we can approximate $L'$ arbitrarily closely by invertible 
matrices and hence we obtain 
$$
 t^{n-m} \mathrm{per}_m(X)  \in \Omega_n .
$$
Mulmuley and Sohoni~\cite{gct1} proposed to prove that 
$t^{n-m} \mathrm{per}_m(X)  \not\in \Omega_n$, which is stronger 
than $\mathrm{dc}(m) > n$, but which has the benefit that this problem 
can be naturally approached by tools from algebraic geometric. 
In particular, methods from geometric invariant theory 
can be brought into play. 

The basic strategy for proving lower bounds is now to exhibit a polynomial 
function 
$$ 
 R\colon\mathrm{Sym}^n\mathbb{C}^{n^2} \to \mathbb{C}
$$
that vanishes on $\Omega_n$, but not 
on the padded permanent $t^{n-m} \mathrm{per}_m(X)$.  
Theorem~\ref{th:tops} tells us that this strategy ``in principle'' must work, 
but how on earth could we find such a function $R$?

The idea is to exploit the symmetries. The determinant variety $\Omega_n$ 
clearly is invariant under the action of the group $\mathrm{GL}_{n^2}$ on $\mathrm{Sym}^n\mathbb{C}^{n^2}$. 

We consider the vanishing ideal
$$
 I(\Omega_n) =\{ R \mid \mbox{$R$ vanishes on $\Omega_n$} \} ,
$$
which is invariant under the action of $\mathrm{GL}_{n^2}$.
We bring now the representation theory of $\mathrm{GL}_{n^2}$ 
into play and try to understand which types of irreducible 
$\mathrm{GL}_{n^2}$-modules appear in $I(\Omega_n)$. 

\subsection{A primer on representation theory}

Our treatment here is extremely brief. Basically, we just recall 
definitions and introduce notations. E.g., see
\cite{FH:91} for more information on this classical topic.

It is well-known that the isomorphism types of irreducible (rational) 
$\mathrm{GL}_{n^2}$-modules can be labelled by highest weights, 
which we can view as $\lambda\in\mathbb{Z}^{n^2}$ such that 
$\lambda_1\ge\cdots \ge \lambda_{n^2}$.  
The Schur-Weyl module $V_\lambda=V_\lambda(\mathrm{GL}_{n^2})$ denotes an 
irreducible $\mathrm{GL}_{n^2}$-module of highest weight $\lambda$. 

If $\lambda_{n^2}\ge 0$, then $\lambda$ is a partition of {\epsilonm length} 
$\epsilonll(\lambda):= \#\{ i \mid \lambda_i \ne 0 \} \le n^2$ and {\epsilonm size} 
$|\lambda| := \sum_i \lambda_i$. 
We briefly write $\lambda\vdash_{n^2} |\lambda|$ for this. 

\begin{example}
1. If $\lambda=(\delta,\ldots,\delta)$ for $\delta\in\mathbb{Z}$, then 
$V_\lambda=\mathbb{C}$ with the operation 
$g\cdot 1 = \mathrm{det}(g)^{\delta}$. 

2. If $\lambda=(\delta,0,\ldots,0)$ for $\delta\in\mathbb{N}$, then 
$V_\lambda = \mathrm{Sym}^{\delta} \mathbb{C}^{n^2}$. 
\epsilonnd{example}

The group $\mathrm{GL}_{n^2}$ acts on $\mathrm{Sym}^d\mathrm{Sym}^n\mathbb{C}^{n^2}$, 
and we are interested in its isotypical decomposition:
\begin{equation}\lambdabel{eq:plethysm}
 \mathrm{Sym}^d\mathrm{Sym}^n\mathbb{C}^{n^2} = \bigoplus_{\lambda\vdash dn} \mathrm{pleth}_n(\lambda) V_\lambda .
\epsilonnd{equation}
The arising multiplicities $\mathrm{pleth}_n(\lambda)\in\mathbb{N}$ are called {\epsilonm plethysm coefficients}. 

\begin{remark}
The decomposition of $\mathrm{Sym}^d\mathrm{Sym}^n\mathbb{C}^{2}$ describes the invariants and covariants of binary forms 
of degree $n$. This was a subject of intense study in the 19th century and 
famous names like Cayley, Sylvester, Clebsch, Gordan, Hermite, Hilbert, $\ldots$ 
are associated with it (e.g., see \cite{schur:68,sturmfels:93}). 
However, in the above situation of forms of many variables, 
little is known. 
\epsilonnd{remark}

We now go back to the vanishing ideal of $\Omega_n$ and ask for the isotypical 
decomposition of the degree $d$ component of its 
vanishing ideal $I(\Omega_n)$: 
\begin{equation}\lambdabel{eq:mdet}
 I(\Omega_n)_d = \bigoplus_{\lambda\vdash dn} \mathrm{multdet}_n(\lambda) V_\lambda .
\epsilonnd{equation}
Our goal is to get some information about the arising 
multiplicities $\mathrm{multdet}_n(\lambda)$. 
It will be convenient to say that the elements of the isotypical component 
$\mathrm{multdet}_n(\lambda) V_\lambda$ contain the {\epsilonm equations for $\Omega_n$ of type $\lambda$}.  
Representation theory tells us that the equations ``come in modules''.
The {\epsilonm multiplicity $\mathrm{multdet}_n(\lambda)$}, multiplied by $\dim V_\lambda$, 
tells us how many linearly independent 
equations of type $\lambda$ there are. 

In order to say something about $\mathrm{multdet}_n(\lambda)$, we recall the following 
crucial quantity.

\begin{definition}\lambdabel{def:KronCoeff}
Let $\lambda_i\vdash_{m_i} N$, $i=1,2,3$, be three partitions of $N$ 
with length $\epsilonll(\lambda_i) \le m_i$. Their {\epsilonm Kronecker coefficient} 
is defined as the multiplicity of the irreducible 
$\mathrm{GL}_{m_1}\times\mathrm{GL}_{m_2}\times \mathrm{GL}_{m_3}$-module in 
$\mathrm{Sym}^N\big(\mathbb{C}^{m_1}\otimes \mathbb{C}^{m_2}\otimes \mathbb{C}^{m_3}\big)$: 
$$
 k(\lambda_1,\lambda_2,\lambda_3) := \mathrm{mult}\Big(
  V_{\lambda_1}\otimes V_{\lambda_2}\otimes V_{\lambda_3}, \mathrm{Sym}^N \big(\mathbb{C}^{m_1}\otimes \mathbb{C}^{m_2}\otimes \mathbb{C}^{m_3}\big) \Big) .
$$
\epsilonnd{definition}

It is well-known that, by Schur-Weyl duality, there is also an interpretation of Kronecker coefficients 
in terms of representations of the symmetric group $S_N$: we have 
$$
 k(\lambda_1,\lambda_2,\lambda_3) = \dim \big( [\lambda]\otimes [\mu]\otimes [\nu] \big)^{S_N},
$$ 
where $[\lambda]$ denotes an irreducible $S_N$-module of type $\lambda$ (Specht module). 

Unfortunately, despite being fundamental, Kronecker coefficients are not well understood.
We believe that they should count some efficiently describable objects, but such a description 
has so far only be achieved in special cases (notably, if one of the partitions is a hook, cf.~\cite{blasiak:12}).
Computer science has developed models to express this question in a rigorous way. 
We encode partitions as lists of binary encoded integers. 

\begin{problem}
Is the function $(\lambda_1,\lambda_2,\lambda_3) \mapsto k(\lambda_1,\lambda_2,\lambda_3)$ 
in the complexity class $\#\mathrm{P}$? 
\epsilonnd{problem}

We will see that 
the case where two of the three partitions are equal and of rectangular shape 
$n\times d = (d,\ldots,d)$ ($n$ times), is of special interest to us. 
We therefore define 
\begin{equation}\lambdabel{def:RKron}
 k_n(\lambda) := k(\lambda,n\times d, n\times d) \quad 
 \mbox{ for $\lambda\vdash dn$.} 
\epsilonnd{equation}

\subsection{Obstructions} 

The coordinate ring of $\Omega_n$ consists of the restrictions 
of polynomial functions to $\Omega_n$ and can be described as 
$$
 \mathbb{C}[\Omega_n] := \mathbb{C}\big[\mathrm{Sym}^n\mathbb{C}^{n^2}\big]/I(\Omega_n) . 
$$
The multiplicity of the irreducible $\mathrm{GL}_{n^2}$-module $V_\lambda$ in $\mathbb{C}[\Omega_n]$
can be expressed as 
\begin{equation}\lambdabel{def:ktilde}
 \tilde{k}_n(\lambda) := \mathrm{pleth}_n(\lambda) - \mathrm{multdet}_n(\lambda) ,
\epsilonnd{equation}
which we shall call {\epsilonm GCT-coefficients}. 
The following theorem, which is due to Mulmuley \& Sohoni~\cite{gct2}, 
shows that $\tilde{k}_n(\lambda)$ is upper bounded by the special Kronecker coefficients $k_n(\lambda)$. 

A refinement of this result can be found in~\cite{BLMW:11}.  

\begin{theorem}[Mulmuley and Sohoni]\lambdabel{th:ms}
We have $\tilde{k}_n(\lambda) \le k_n(\lambda)$ for $\lambda\vdash_{n^2} dn$.  
\epsilonnd{theorem}

We explain now how we intend to apply this theorem for the purpose of lower bounds.
(Currently, this plan could not yet be realized, and we will explain below some of the 
difficulties encountered with its realization.)

Suppose that $k_n(\lambda) = 0$. Then Theorem~\ref{th:ms} implies that 
$\mathrm{multdet}_n(\lambda) = \mathrm{pleth}_n(\lambda)$. Looking at 
the decompositions~\epsilonqref{eq:plethysm} and~\epsilonqref{eq:mdet}, 
we infer that any polynomial 
$R\in\mathrm{Sym}^d\mathrm{Sym}^n\mathbb{C}^{n^2}$ of type~$\lambda$ vanishes on the 
determinant variety $\Omega_n$. 
If we are lucky, and additionally, 
some $R$ of type $\lambda$ satisfies 
$R(t^{n-m}\mathrm{per}_m) \ne 0$, then we can conclude that 
the padded permanent $t^{n-m}\mathrm{per}_m$ does not lie in $\Omega_n$ .
Therefore the lower bound $\mathrm{dc}(m) >n$ would follow. 

We call such a partition $\lambda$ an 
{\epsilonm (occurrence) obstruction proving $\mathrm{dc}(m) > n$}.  

The nonvanishing condition for $R$ has the following consequences.
First of all, we must have $\mathrm{pleth}_n(\lambda)>0$. 
Moreover, we have the following constraints 
on the shape of $\lambda$. 

\begin{theorem}[Landsberg and Kadish]\lambdabel{th:kl}
If there exists $R\in\mathrm{Sym}^d\mathrm{Sym}^n\mathbb{C}^{n^2}$ of type $\lambda\vdash_{n^2} dn$ 
such that $R(t^{n-m}g) \ne 0$ for 
some  form $g$ of degree~$m$ in $\epsilonll\le n^2$ variables, then 
$\epsilonll(\lambda) \le \epsilonll +1$ and $\lambda_1 \ge |\lambda| ( 1- m/n)$.
\epsilonnd{theorem}

The first assertion is from \cite{BLMW:11} 
and the second is from \cite{kadish-landsberg:14}. 
We omit the proof. 

Hence an obstruction $\lambda$ has relatively few rows and 
almost all of its boxes are in its first row.
More specifically, in our situation, we have $\epsilonll=m^2$. 

Therefore, a hypothetical sequence $(\lambda^m)$ of obstructions certifying 
at least $m^2/2\le \mathrm{dc}(m)$ must satisfy 
$\epsilonll(\lambda^m)\le m^2 +1$ and 
$\lim_{m\to\infty} \lambda^m_1/|\lambda^m| = 1$. 

To further simplify, let us now forget about the nonvanishing 
of $R$ on the padded permanent and 
make the following definition. 

\begin{definition}
An {\epsilonm obstruction for forms of degree~$n$} 
is a partition $\lambda\vdash_{n^2} dn$, for some $d$, such that 
$k_n(\lambda) = 0$ and $\mathrm{pleth}_n(\lambda) >0$.
\epsilonnd{definition}
 
\begin{proposition}
Assume there exists an obstruction~$\lambda$ for forms of degree~$n$ 
with $\epsilonll=\epsilonll(\lambda)$ rows. Then a generic polynomial 
$f\in\mathrm{Sym}^n\mathbb{C}^{\epsilonll}$ of degree~$n$ in $\epsilonll$ variables
satisfies $\mathrm{dc}(f) > n$. 
\epsilonnd{proposition}

\begin{proof} 
The assumption $\mathrm{pleth}_n(\lambda) >0$ implies that there exists some 
homogeneous polynomial function
$R\colon\mathrm{Sym}^n\mathbb{C}^{n^2} \to \mathbb{C}$ of type $\lambda$; cf.~\epsilonqref{eq:plethysm}.
Moreover, we may assume that the restriction of~$f$ to $\mathrm{Sym}^n\mathbb{C}^{\epsilonll}$ does not vanish. 
(For this, one needs to know that $\mathrm{pleth}_n(\lambda)$ does not change when removing 
zeros from $\lambda$.)
By Theorem~\ref{th:ms}, $k_n(\lambda)=0$ implies 
$\tilde{k}_n(\lambda)=0$ and hence $R$ vanishes on ~$\Omega_n$;
cf. \epsilonqref{eq:plethysm}. 
For a generic $f\in\mathrm{Sym}^n\mathbb{C}^{\epsilonll}$ we have $R(f)\ne 0$. 
Hence $f \not\in \Omega_n$, which proves that $\mathrm{dc}(f) > n$.
\epsilonnd{proof}

\begin{example}(Ikenmeyer~\cite{ike:12b})\lambdabel{ex:obstruction}
$\lambda=(13,13,2,2,2,2,2)$ is an obstruction for forms of degree~$3$ in $7$ variables.
Indeed, $|\lambda|= 36 = 12\cdot 3$, $\epsilonll(\lambda) =7$ and one can check 
with computer calculations that 
$\mathrm{pleth}_3(\lambda) = 1$ and $k_3(\lambda)= 0$. 
(We compute Kronecker coefficients with an adaption by 
J.~H\"uttenhain of a code originally written by H.~Derksen.) 
In this situation, there is (up to scaling) a unique 
highest weight function
$R\colon \mathrm{Sym}^3\mathbb{C}^9 \to \mathbb{C}$ of degree~$12$ and type $\lambda$. 
This function $R$ vanishes on $\Omega_3$. 

Let us point out that the dimension of the 
``search space'' $\mathrm{Sym}^{12} \mathbb{C}^{165}$ in which $R$ lives is 
enormous: we have  
$\mathrm{Sym}^3\mathbb{C}^9\simeq \mathbb{C}^{165}$ and 
$\dim \mathrm{Sym}^{12} \mathbb{C}^{165} \approx 1.3 \cdot 10^{19}$. 
We have found the ``needle in a haystack'' with the help of 
represention theory and extensive calculations! 
It should also be emphasized that it is possible to describe $R$ in a concise way using 
symmetrizations, cf.~\cite{ike:12b}.
\epsilonnd{example}

The following is a major open problem!  

\begin{problem}\lambdabel{problem:find-obstructions}
Find families of obstructions for forms with few rows.
\epsilonnd{problem}

\subsection{Sketch of proof of Theorem~\ref{th:ms}}

\subsubsection{Symmetries of the determinant}

The symmetries of $\mathrm{det}_n$ are captured by the 
{\epsilonm stabilizer group} 
$$
 \mathrm{stab}_n := \Big\{ g\in \mathrm{GL}(\mathbb{C}^{n^2}) \mid 
    \mathrm{det}(g(X)) = \mathrm{det}(X) \Big\} ,
$$
where we interpret in this formula $X$ as a vector of length $n^2$. 
For $A,B\in\mathrm{SL}_n$ we consider the following linear map given by matrix multiplication: 
\begin{equation}\lambdabel{eq:gAB}
 g_{A,B} \colon \mathbb{C}^{n\times n} \to \mathbb{C}^{n\times n},\, 
 X \mapsto AXB .
\epsilonnd{equation}
We have 
$\mathrm{det}(AXB) = \mathrm{det}(A)\mathrm{det}(X)\mathrm{det}(B) = \mathrm{det}(X)$. 
Hence $g_{A,B} \in \mathrm{stab}_n$.  
Are these all elements of the stabilizer group of $\mathrm{det}_n$? 
No, the transposition 
$\tau\colon\mathbb{C}^{n\times n} \to \mathbb{C}^{n\times n},\, X\mapsto X^T$
clearly also belongs to $\mathrm{stab}_n$.

The following result due to Frobenius~\cite{Frobdet} in fact 
states that each element of $\mathrm{stab}_n$ is of the form 
$g_{A,B}$ or $\tau g_{A,B}$. 
(This was rediscovered later by Dieudonn\'e~\cite{dieu:49}.) 
We skip the proof. 

\begin{theorem}[Frobenius]\lambdabel{th:frobenius} 
The stabilizer group $\mathrm{stab}_n$ of $\mathrm{det}_n$ is generated by 
$\tau$ and the $g_{A,B}$ for $A,B\in\mathrm{SL}_n$. 
We have 
$$
 \mathrm{stab}_n \simeq (\mathrm{SL}_n \times \mathrm{SL}_n) /\mu_n \rtimes \mathbb{Z}_2 ,
$$
where $\mu_n := \{ t\mathrm{id}_n \mid t^n =1 \}$. 

\epsilonnd{theorem}

\subsubsection{Multiplicities in the coordinate ring of the orbit of $\mathrm{det}_n$}

In algebraic geometry, one defines a {\epsilonm regular function} 
$\varphi\colon\mathrm{GL}_{n^2}\cdot \mathrm{det}_n \to \mathbb{C}$ as a function 
such that each point of the orbit $\mathrm{GL}_{n^2}\cdot \mathrm{det}_n$ 
has an open neighborhood on which $\varphi$ can be 
expressed as the quotient of two rational functions. 
We denote by $\mathbb{C}[\mathrm{GL}_{n^2}\cdot \mathrm{det}_n]$ the ring of 
regular functions on the orbit. 

Let us point out that the orbit is a smooth algebraic variety, 
that is well understood in various senses. By going over 
to the orbit closure $\Omega_n$, one adds limit points at 
the boundary, and we expect the situation to become very complicated. 
(Compare \cite{lamare:13,buik:15} for some results.) 

Clearly, we have the following  inclusion of rings of regular functions: 
$$
 \mathbb{C}[\Omega_n] \subseteq \mathbb{C}\big[\mathrm{GL}_{n^2}\cdot \mathrm{det}_n\big] .
$$
By comparing multiplicities, it follows that for $\lambda\vdash_{n^2} dn$, 
\begin{eqnarray*}
\tilde{k}_n(\lambda) = \mathrm{pleth}_n(\lambda) - \mathrm{multdet}_n(\lambda) &=& \mbox{ multiplicity of $V_\lambda$ in $\mathbb{C}[\Omega_n]$} \\
   & \le &  \mbox{ multiplicity of $V_\lambda$ in $\mathbb{C}[\mathrm{GL}_{n^2}\cdot \mathrm{det}_n]$} \\
   & = & \dim \big(V_\lambda \big)^{\mathrm{stab}_n} \quad\mbox{(algebraic Peter-Weyl theorem)}\\
   & \le & k_n(\lambda) \quad\mbox{(see below)}.
\epsilonnd{eqnarray*}
The {\epsilonm Peter-Weyl theorem} is a well-known theorem from harmonic analysis,  
telling us about the irreducible $G$-modules in the space $L^2(G,\mathbb{C})$ 
of quadratic integrable functions on a compact Lie group~$G$.  
(If $G$ is finite, this is just the well-known decomposition of the 
regular represention.) 
For the second equality above we used an
algebraic version of the Peter-Weyl theorem; 
cf. \cite[Chap.~II, sect.~3, Thm.~3]{kraf:84}
or \cite[Section~7.3]{procesi:07}.

We now justify the last inequality. It is here that Kronecker coefficients 
enter the game!
Schur-Weyl duality implies that by restricting the $\mathrm{GL}_{n^2}$-action of $V_\lambda(\mathrm{GL}_{n^2})$ 
with respect to the homomorphism 
$\mathrm{GL}_n\times\mathrm{GL}_n \to \mathrm{GL}_{n^2},\, (A,B) \mapsto A \otimes B$, we obtain 
$$
 V_\lambda(\mathrm{GL}_{n^2}) \downarrow_{\mathrm{GL}_n\times\mathrm{GL}_n} = \bigoplus_{\mu,\nu\vdash_n |\lambda|}
  k(\lambda,\mu,\nu) \, V_\mu(\mathrm{GL}_n) \otimes V_\nu(\mathrm{GL}_n) .
$$
We look now for $\mathrm{SL}_n\times\mathrm{SL}_n$-invariants. They occur on the 
right-hand side only if $\mu=\nu=n\times d$ and $|\lambda| = dn$. 
Note that $A\otimes B$ is just another way of writing $g_{A,B}$; see \epsilonqref{eq:gAB}.
Using Theorem~\ref{th:frobenius}, we obtain 
$$
 \dim \big(V_\lambda(\mathrm{GL}_{n^2})\big)^{\mathrm{stab}_n} \le \dim V_\lambda(\mathrm{GL}_{n^2})^{\mathrm{SL}_n\times\mathrm{SL}_n} 
   = k(\lambda,n\times d, n\times d) = k_n(\lambda) .
$$
This completes the proof of Theorem~\ref{th:ms}.

\subsection{Obstructions must be gaps} 

We address now the question of how to exhibit obstructions for forms. 
Example~\ref{ex:obstruction} was found with extensive calculations.
We will see here that, in a certain sense, obstructions are quite rare, 
or at least hard to find. 

Progress on Problem~\ref{problem:find-obstructions} is thus imperative. 
We don't want to hide the fact that we do not know whether there exist 
enough obstructions for achieving the desired lower bounds on determinantal complexity. 
In fact, the state of the art is that so far, no lower bound on $\mathrm{dc}(m)$ 
has been obtained along these lines. However, let us point out 
that in the related, but simpler situation of border rank  of tensors, 
lower bounds have been proven by exhibiting obstructions; see~\cite{BI:13}. 

We consider the following  set of highest weights
$$
 K_n := \big\{ \lambda \mid \mbox{$\lambda \vdash_{n^2} dn$ for some $d$ and $k_n(\lambda) > 0$} \big\} .
$$
From Definition~\ref{def:KronCoeff} it easily follows that 
$\lambda,\mu\in K_n$ implies $\lambda +\mu \in K_n$. 
Moreover, $0\in K_n$. Hence $K_n$ is a monoid.
(It follows from general principles that $K_n$ is 
finitely generated; cf.~\cite{brion:87}.)

\begin{example}
To illustrate the next step, consider the submonoid 
$M:=\{0,3,5,6,8,9,\ldots\}$ of $\mathbb{N}$, which clearly 
generates the group $\mathbb{Z}$. 
From $sx \in M$, $s\ge 1$, we cannot deduce that $x\in M$, 
due to the presence of the ``holes'' $1,2,4,7$. 
Filling in these holes, we obtain the monoid $\mathbb{N}$. 
The holes are usually called the {\epsilonm gaps of the monoid $M$}; cf.~\cite{alfonsin:05}. 
In general, one calls the process of filling in the gaps {\epsilonm saturation}. 
\epsilonnd{example}

In our situation of interest, we make the following definition. 

\begin{definition}
The {\epsilonm saturation of $K_n$} is the set of partitions $\lambda$ 
with $\epsilonll(\lambda)\le n^2$ such that 
$|\lambda|$ is a multiple of~$n$ and there exists a ``stretching factor'' 
$s\ge 1$ satisfying $s\lambda \in K_n$.
The {\epsilonm gaps} of $K_n$ are the elements in the saturation of $K_n$ 
that don't lie in $K_n$. 
\epsilonnd{definition}

\begin{remark}
To fully justify the naming ``saturation'' here, one has to show that 
the group generated by $K_n$ consists of all $\lambda\in\mathbb{Z}^{n^2}$ such that 
$n$ divides $\sum_i \lambda_i$. (For $n\ge 7$ this was  shown in \cite{ik-pa:15}; 
for $n=2$ it is false.) 
\epsilonnd{remark}

The following result is due to~\cite{buci:09}. 

\begin{theorem}[B, Christandl, Ikenmeyer]\lambdabel{th:buci}
The saturation of the monoid $K_n$ equals the 
set of all partitions $\lambda$ with $\epsilonll(\lambda)\le n^2$ 
such that $|\lambda|$ is a multiple of $n$.
\epsilonnd{theorem}

This result implies that obstructions 
must be gaps of the monoid $K_n$. 
The relevance of Theorem~\ref{th:buci} 
is that it excludes the use of asymptotic 
techniques for finding obstructions.

 

Theorem~\ref{th:ms} states that $\tilde{k}_n(\lambda) \le k_n(\lambda)$. 
However, we only need $\tilde{k}_n(\lambda) = 0$
for implementing our strategy of proving lower bounds. 
Indeed, 
the replacement of $\tilde{k}_n(\lambda)$ by the Kronecker coefficient~$k_n(\lambda)$ 
corresponds to replacing the coordinate ring of the orbit 
closure by the larger coordinate ring of the orbit, 
and this was only done because we better understand the latter.

So one might hope that Theorem~\ref{th:buci} 
fails for the smaller multiplicities $\tilde{k}_n$. 
Unfortunately, this doesn't turn out to be the case. 
Before stating the next result, we introduce a 
certain combinatorial conjecture. 
 
A {\epsilonm Latin square of size~$n$} is map $T\colon [n]^2 \to [n]$,
viewed as an $n\times n$ matrix with entries in~$[n]$, 
such that in each row and each column each entry in~$[n]$ 
appears exactly once.
So in each column and row we get a permutation of $[n]$. 
The column sign of $T$ is defined as the product of the signs of 
column permutations. The Latin square~$T$ is called 
{\epsilonm column-even} if this sign equals one, otherwise $T$ 
is called {\epsilonm column-odd}. 
See Figure~\ref{fig:LS} for an illustration.

\begin{figure}[h]
\begin{center}
$$\begin{array}{cccc}
-&+&-&-\\
1&2&3&4\\
4&1&2&3\\
3&4&1&2\\
2&3&4&1
\epsilonnd{array}$$
\epsilonnd{center}
\caption{\small A Latin square with column-sign $-1$.}\lambdabel{fig:LS}
\epsilonnd{figure}

It is an easy exercise to check that if $n>1$ is odd, then there are 
as many column-even Latin squares of size~$n$ as there are 
column-odd Latin squares of size~$n$.

The Alon-Tarsi conjecture~\cite{AT:92} states that if $n$ is even, then  
the number of column-even Latin squares of size~$n$ is different from 
the number of column-odd Latin squares of size~$n$. 
This conjecture is known to be true if $n=p\pm 1$ where $p$ is a prime, 
cf.~\cite{Dri:98,Gly:10}.

The following result is due to Kumar~\cite{Kum:15}. 
(Note that, in contrast with Theorem~\ref{th:buci}, 
it only makes a statement about the $\lambda$ 
with $\epsilonll(\lambda)\le n$.)

\begin{theorem}[Kumar]
If the Alon-Tarsi conjecture holds for $n$, then 
for all $\lambda$ with $\epsilonll(\lambda) \le n$ such that $|\lambda|$ is a multiple of~$n$, 
we have $\tilde{k}_n(n\lambda) >0$.
\epsilonnd{theorem}

In fact, it is possible to obtain an unconditional result 
at the price of losing the information about the specific 
stretching factor~$n$.
The following result is from~\cite{BHI:15}. 

\begin{theorem}[B, H\"uttenhain, Ikenmeyer]
For all $\lambda$ with $\epsilonll(\lambda)\le n$ such that $|\lambda|$ is a multiple of~$n$, 
there exists $s\ge 1$ such that $\tilde{k}_n(s\lambda) >0$.
\epsilonnd{theorem}

\section{Positivity of Kronecker coefficients}

Motivated by the attempt described in the previous section, 
notabable progress was made about understanding when Kronecker coefficients are positive.  
We report on this in the remainder of this survey. 

\subsection{Testing positivity is NP-hard}

It is known that testing the positivity of Littlewood\-Richardson coefficients 
can be done in polynomial time; cf~\cite{gct3,deloera:06,bu-ik:13}. 
Mulmuley conjectured~\cite{gct6} that testing positivity of Kronecker coefficients 
can be done in polynomial time as well. 
For {\epsilonm fixed~$m$} and partitions $\lambda,\mu,\nu$ of {\epsilonm length at most~$m$} 
this is true, see ~\cite{cdw:12}. 

However, an exciting recent result~\cite{ik-m-w:15}
shows that in general, this is not the case. 

For the following hardness results, we may even assume that the partitions are given as 
lists of integers encoded in unary.
(A positive integer $m$ encoded in unary has size $m$; thus considering unary 
encoding makes the problem easier.) 

\begin{theorem}[Ikenmeyer, Mulmuley, Walter]\lambdabel{th:imw}
Testing positivity of  Kronecker coefficients is an NP-hard problem.

\epsilonnd{theorem}

We are going to outline the proof.
By a {\epsilonm 3D-relation} we shall understand a finite subset $R$ 
of~$\mathbb{N}^3$. 
For $i\in\mathbb{N}$ we set 
$$
 x_R(i) := \#\{(x,y,z) \in R \mid x=i \} , 
$$ 
and we call the sequence $x_R:= (x_R(0),x_R(1),\ldots)$ 
the $x$-marginal of $R$. 
We may interpret $x_R$ as a partition of $|R]$ 
if the entries of $x_R$ are monotonically decreasing. 
(There is no harm caused by the fact that the indexing 
of $x_R$ starts with $0$.)
Similarly, we define the $y$-marginal $y_R$ and the 
$z$-marginal $z_R$ of $R$. 
Note that if $R$ is contained in the discrete cube $\{0,\ldots,m-1\}^3$, then 
$x_R,y_R,z_R$ have at most $m$ nonzero components.
The problem of reconstructing $R$ from its marginals 
is sometimes called ``discrete tomography''. 

We call a 3D-relation $R$ a {\epsilonm pyramid} if $(x,y,z) \in R$ implies 
$(x',y',z') \in R$ for all $(x',y',z') \in \mathbb{N}^3$ such that 
$x'\le x$, $y'\le y$, $z'\le z$. 
In the literature, one often calls pyramids {\epsilonm plane partitions}. 
In fact, they are just the 3D-analogues of Young diagrams.

Let $\lambda'$ denote the partition conjugate to $\lambda$ 
obtained by a reflection of its Young diagram at the main diagonal. 

\begin{definition}
For $\lambda,\mu,\nu\vdash d$ we denote by 
$t(\lambda,\mu,\nu)$ the number of 3D-relations $R$ with 
$x$-marginal $\lambda'$, $y$-marginal $\mu'$, and $z$-marginal $\nu'$.
Moreover, let $p(\lambda,\mu,\nu)$ denote the number of 
pyramids $R$ with the marginals $\lambda',\mu',\nu'$.
\epsilonnd{definition}

The following result was previously proved by Manivel~\cite{mani:97} 
and rediscovered in~\cite{BI:13,ik-m-w:15}; compare also Vallejo~\cite{vallejo:00}.
 
\begin{lemma}\lambdabel{le:pkt}
We have $p(\lambda,\mu,\nu) \le  k(\lambda,\mu,\nu) \le t(\lambda,\mu,\nu)$
for $\lambda,\mu,\nu\vdash d$. 
\epsilonnd{lemma}

\begin{proof}
Recall that $[\lambda'] \simeq [\lambda] \otimes [1^d]$, where $d=|\lambda|$. 
Suppose that $\lambda',\mu',\nu'$ have at most $m$ parts. 
Then we have 
\begin{eqnarray*}
k(\lambda,\mu,\nu)  &=& \mathrm{mult}([\lambda] \otimes [\mu] \otimes [\nu], [d]) \\
 & = & \mathrm{mult}([\lambda'] \otimes [\mu'] \otimes [\nu'], [1^d]) \\
 & = & \mathrm{mult}\big(V_{\lambda'}(\mathrm{GL}_m) \otimes V_{\mu'}(\mathrm{GL}_m) \otimes V_{\nu'}(\mathrm{GL}_m), \Lambda^d(\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m)\big) ,
\epsilonnd{eqnarray*}
where for the last equality we have used Schur-Weyl duality. 

Let $e_j$ denote the $j$th canonical basis vector of $\mathbb{C}^m$. 
To a 3D-relation 
$R =\{ (x_i,y_i,z_i) \mid 1\le i \le d\} \subseteq \{0,\ldots,m-1\}^3$ 
such that $|R|=d$, we assign the vector (only defined up to sign) 
$$
  v_R := \pm\wedge_{i=1}^d (e_{x_i} \otimes e_{y_i} \otimes e_{z_i}) \ \in\ 
 \wedge^d (\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m) .
$$
Note that the $v_R$ form a basis of $\wedge^d (\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m)$. 
In fact, $v_R$ is a weight vector of weight $(x_R,y_R,z_R)$, since 
for a triple $g=(\mathrm{diag}(a_0,\ldots,a_{m-1}),\mathrm{diag}(b_0,\ldots,b_{m-1}), \mathrm{diag}(c_0,\ldots,c_{m-1}))$ 
of invertible diagonal matrices we have  
$$
 g\cdot v_R = 
 a_0^{x_R(0)}\cdots a_{m-1}^{x_R(m-1)}  b_0^{y_R(0)}\cdots b_{m-1}^{y_R(m-1)}  c_0^{z_R(0)}\cdots c_{m-1}^{z_R(m-1)}\,  v_R .
$$
We conclude that $t(\lambda,\mu,\nu)$ equals the dimension of the weight space of 
weight $(\lambda',\mu',\nu')$ in $\Lambda^d(\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m)$. 

At the beginning of the proof, we observed that 
$k(\lambda,\mu,\nu)$ equals the multiplicity of 
$V_{\lambda'}(\mathrm{GL}_m) \otimes V_{\mu'}(\mathrm{GL}_m) \otimes V_{\nu'}(\mathrm{GL}_m)$
in $\Lambda^d(\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m)$,
which is the dimension of the vector space of highest weight vectors
of weight $(\lambda',\mu',\nu')$ in $\Lambda^d(\mathbb{C}^m\otimes\mathbb{C}^m\otimes \mathbb{C}^m)$. 
So we conclude that $k(\lambda,\mu,\nu)\le t(\lambda,\mu,\nu)$. 

Finally, if $R$ is a pyramid, then it is easy to check that 
$(g_1,g_2,g_3) \cdot v_R = v_R$, where $g_1,g_2,g_3$ are invertible upper triangular matrices 
with $1$'s on the diagonal. In this case, $v_R$ is therefore a highest weight vector.  
This implies $p(\lambda,\mu,\nu)\le k(\lambda,\mu,\nu)$. 
\epsilonnd{proof}

We will show now that certain constraints on the marginals of 
 a 3D-relation~$R$ enforce that $R$ must be a pyramid. 

The distance of the {\epsilonm barycenter} 
$b_R := \frac{1}{|R|}\sum_{p\in R} p$
of~$R$ to the linear hyperplane 
orthogonal to the diagonal $(1,1,1)$ 
is given by $h_R := b_R \cdot (1,1,1)^T$,  
up to the scaling factor $\sqrt{3}$. 
The distance~$h_R$ can be expressed in terms of the 
marginals of $R$ by  
\begin{equation}\lambdabel{eq:margy}
  \mbox{$ |R|\, h_R = \sum_{(x,y,z)\in R} (x+y+z) 
     = \sum_{i} i\, (x_R(i)  + y_R(i) + z_R(i) ) $.} 

\epsilonnd{equation}
For $s\ge 1$ we consider the simplex 
$P(s) := \{ (x,y,z) \in\mathbb{N}^3 \mid x+y+z \le s-1\}$,  
which has the cardinality $|P(s)| = s(s+1)(s+2)/6$. 
For $d\ge 1$ we define $s(d)$ as the maximal natural number~$s$ such that 
$|P(s)| \le d$. 

Assume now that a 3D-relation $R$ satisfies 
$P(s)\subseteq R \subset P(s+1)$ for some $s$. 
Then necessarily $s=s(d)$, where $d := |R|$. 
In this situation, it is easy to see that $h_R = h(d)$, where 
\begin{equation}\lambdabel{eq:bary}
 \mbox{$h(d) :=  \frac{|P(s)|}{d}\,  h_{P(s)} + (1 - \frac{|P(s)|}{d} )\, s $.}
\epsilonnd{equation}
If $\lambda',\mu',\nu'$ denote the marginals of $R$, then we have by \epsilonqref{eq:margy}, 
\begin{equation}\lambdabel{def:simplex-like}
  \sum_{i}  i\, (\lambda'_i + \mu'_i +\nu'_i) = d\, h(d) .
\epsilonnd{equation}
We call a triple $\lambda,\mu,\nu \vdash d$ of partitions  
{\epsilonm simplex-like} if \epsilonqref{def:simplex-like} holds. 

\begin{lemma}\lambdabel{le:p=k=t}
Any 3D-relation~$R$, whose marginals are simplex-like, is a pyramid.
Hence $k(\lambda,\mu,\nu) = t(\lambda,\mu,\nu)$ if $(\lambda,\mu,\nu)$ is simplex-like.
\epsilonnd{lemma}

\begin{proof}
The first assertion is easy to prove  
and the second one follows with Lemma~\ref{le:pkt}.
\epsilonnd{proof}

The following result was shown in~\cite{BDLG:00}. 

\begin{theorem}[Brunetti, Del Lungo, G\'erard]\lambdabel{th:brunetti}
Deciding $t(\lambda,\mu,\nu)>0$ is an NP-hard problem. 
\epsilonnd{theorem}

The catch is that the reduction in the proof of this theorem 
from 3D-matching is such 
that one can actually reduce to simplex-like triples 
$(\lambda,\mu,\nu)$ of partitions. This completes 
our sketch of the proof of Theorem~\ref{th:imw}.
In fact, the NP-hardness reduction in the proof of Theorem~\ref{th:brunetti}
leads to an efficient and explicit way to produce many gaps of 
the Kronecker monoid. We are not aware of any other way to obtain this result! 
Unfortunately, the reduction breaks down for the most wanted situation of 
partition triples $(\lambda,\mu,\mu)$ where $\mu$ is a rectangle.

In fact, one can prove that $t(\lambda,n\times d, n\times d)>0$ if $\lambda\vdash dn$ 
such that $\epsilonll(\lambda) \le\min\{d^2,n^2\}$, see \cite[Thm.~6.9]{ik-m-w:15}.

From the proof of Theorem~\ref{th:brunetti} one 
obtains the following insights, which show a remarkable  
interplay between computer science and algebraic combinatorics.

\begin{itemize}
\item There is a positive $\#\mathrm{P}$-formula for a subclass of 
triples of partitions, whose positivity of Kronecker coefficients
is NP-hard to decide.

\item The Kronecker monoid has many gaps,  
and we can efficiently compute subexponentially many of them. More specifically,
for any $0<\epsilon <1$ there is $0<a<1$ such that for all~$m$, 
there exist $\Omega(2^{m^a})$ many partition triples 
$(\lambda,\mu,\mu)$ such that 
$k(\lambda,\mu,\mu) = 0$, but there exists $s\ge 1$ with 
$k(s\lambda,s\mu,s\mu) > 0$. Moreover, 
$\epsilonll(\mu) \le m^\epsilon$ and $|\lambda| = |\mu| \le m^3$. 
Finally, there is an efficient algorithm to produce these partitions. 
\epsilonnd{itemize}

Since the reduction breaks down for the most wanted situation of 
partition triples $(\lambda,\mu,\mu)$ where $\mu$ is a rectangle, 
this fails to provide a solution for Problem~\ref{problem:find-obstructions}.

\subsection{Testing asymptotic positivity may be feasible} 

We finish by mentioning a further recent insight.

\begin{definition}
The {\epsilonm asymptotic positivity problem for Kronecker coefficients} 
is the problem of deciding for given $\lambda,\mu,\nu$ 
(in binary encoding) whether $k(s\lambda,s\mu,s\nu) > 0$ for some $s\ge 1$. 
\epsilonnd{definition}

This problem can be rephrased as a membership problem to a (family of) 
polyhedral cones, that we may call {\epsilonm Kronecker cones}. 
They are of relevance for the quantum marginal problem 
of quantum information theory; see
\cite{klya:04,ChrMit06,ChristHarrowMitch07}. 

Theorem~\ref{th:imw} states that the positivity testing problem 
for Kronecker coefficients is NP-hard. 
By contrast, the following recent result~\cite{bcmw:15}
tells us that the asymptotic version of this problem 
should be considerably easier.

\begin{theorem}[B, Christandl, Mulmuley, Walter]\lambdabel{th:aspos}
The asymptotic positivity problem for Kronecker coefficients is in 
$\mathbb{N}P\cap\mathrm{coNP}$. 
\epsilonnd{theorem}

In fact, we have now good reasons to conjecture that the asymptotic positivity problem 
for Kronecker coefficients can be solved in polynomial time. 
In view of the known algorithms and the complicated face structure 
of the Kronecker cones~\cite{ressayre:10,verwa:14}, this is quite surprising.

The proof of Theorem~\ref{th:aspos} 
combines different techniques. 
The containment in $\mathbb{N}P$ is a consequence of the description of the Kronecker cone as the
image of the so-called moment map, which is a consequence of a general result due 
to Mumford~\cite{ness:84}; see also \cite{brion:87}. 
Moment maps are studied in symplectic geometry. 

The basis of the containment in $\mathrm{coNP}$ is a description of the facets 
of the Kronecker cone due to Ressayre~\cite{ressayre:10}. 
Vergne and Walter~\cite{verwa:14} provided a modification of Ressayre's 
description that is efficiently testable, which leads to the containement in $\mathrm{coNP}$. 

\section{Note added in proof}

Since the writing of this survey in the fall of 2015, important progress has been made 
with regard to the feasibility of the attempt outlined in Section~\ref{se:attempt}. 

In a breakthrough work,
Ikenmeyer and Panova~\cite{ik-pa:15} showed that 
the vanishing of rectangular Kronecker coefficients 
cannot be used to prove superpolynomial lower bounds on the 
determinantal complexity of the permanent polynomials! 

Recall that by Theorem~\ref{th:kl}, an occurence obstruction~$\lambda$ 
proving $\mathrm{dc}(m) > n$ necessarily satisfies 
$\epsilonll(\lambda) \le m^2 +1$ and $\lambda_1 \ge |\lambda| ( 1- m/n)$. 
(By a minor modification of the notion of padded permanents, 
we may even assume $\epsilonll(\lambda) \le m^2$.)  

More specifically, Ikenmeyer and Panova proved the following.

\begin{theorem}[Ikenmeyer and Panova]\lambdabel{th:IP}
Let $\lambda\vdash dn$ such that $\epsilonll(\lambda) \le m^2$,
$\lambda_1 \ge |\lambda| ( 1- m/n)$, and assume $n>3m^4$. 
Then $\mathrm{pleth}_n(\lambda) >0$ implies $k_n(\lambda) >0$.
\epsilonnd{theorem}

This result does not yet rule out the occurence based approach 
towards $\mathrm{VP}\ne \mathrm{VNP}$ as outlined in Section~\ref{se:attempt}, 
since it refers to the Kronecker coefficients $k_n(\lambda)$ of 
rectangular partitions and not to the
GCT-coefficients $\tilde{k}_n(\lambda)$.
(Recall those are the multiplicities 
in the coordinate ring of the orbit closure of $\Omega_n$; 
see \epsilonqref{def:ktilde} and Theorem~\ref{th:ms}.) 

However, shortly after the appearance of~\cite{ik-pa:15}, 
B\"urgisser, Ikenmeyer and Panova~\cite{bu-ik-pa:16} proved 
a similarly devastating result for the GCT-coefficients.

\begin{theorem}[B, Ikenmeyer, and Panova]\lambdabel{th:BIP}
Let $\lambda\vdash dn$ such that we have $\epsilonll(\lambda) \le m^2$, 
$\lambda_1 \ge |\lambda| ( 1- m/n)$, and assume $n>m^{25}$. 
Then $\mathrm{pleth}_n(\lambda) >0$ implies $\tilde{k}_n(\lambda) >0$.
\epsilonnd{theorem}

The main ingredient behind the proof of Theorem~\ref{th:BIP}, 
besides a splitting technique as for Theorem~\ref{th:IP}, 
is the encoding of a generating system of highest weight vectors 
in plethysms $\mathrm{Sym}^d\mathrm{Sym}^n V$ by (classes of) tableaux with contents $d\times n$, as well as 
the analysis of their evaluation at tensors of rank one in a combinatorial way. 
This is similar to \cite{bci:10,ike:12b}.  
A further technique is the ``lifting'' of highest weight vectors of $\mathrm{Sym}^d\mathrm{Sym}^n V$, 
when increasing the inner degree~$n$, 
as introduced by Kadish and Landsberg~\cite{kadish-landsberg:14}. 
This is closely related to stability property of the plethysm coefficients
\cite{wei:90,carre-thibon:92,mani:98}. 

Remarkably, for the proof of Theorem~\ref{th:BIP}, the only information 
needed about the orbit closures $\Omega_n$ is that they contain certain padded power sums, 
see also~\cite{buik:15}. 

\subsection{Final remarks} 

Unfortunately, Theorem~\ref{th:BIP} rules out the possibility of proving 
$\mathrm{VP}\ne \mathrm{VNP}$ via occurrence obstructions.

Let us emphasize that there still remains the possibility that 
the approach via representation theoretic obstructions may succeed 
when comparing multiplicities. 
Indeed, if the orbit closure $Z_{n,m}$ of the padded permanent
$t^{n-m} \mathrm{per}_m$ is contained in $\Omega_n$, then 
the restriction defines a surjective $\mathrm{GL}_{n^2}$-equivariant homomorphism 
$\mathbb{C}[\Omega_n]\to\mathbb{C}[Z_{n,m}]$ of the coordinate rings, 
and hence  the multiplicity of the type $\lambda$ in 
$\mathbb{C}[Z_{n,m}]$ is bounded from above by
the GCT-coefficient $\tilde{k}_n(\lambda)$. 
Thus, proving that $\tilde{k}_n(\lambda)$ is strictly smaller 
than the latter multiplicity implies that  
$Z_{n,m}\not\subseteq\Omega_n$. 
Mumuley pointed out to us a paper by 
Larsen and Pink~\cite{lapa:90} that is of 
potential interest in this connection. 

In this context let us remark that~\cite{cdw:12} shows  
that comparing multiplicities by asymptotic methods 
cannot be sufficient for the purpose of complexity separation. 

To conclude, even if the approach via multiplicities should turn out to be impossible 
as well, we should keep in mind that the noncontainment of orbit closures 
in principle can be proved by exhibiting some highest weight vector functions
(see \cite[Prop.~3.3]{BI:13}). Classic invariant theory and representation theory 
should provide guidelines on how to find such functions, even though 
our current understanding of this is very limited. 

\noindent{\bf Acknowledgements.} 
I thank Jesko H\"uttenhain, Christian Ikenmeyer, Joseph Landsberg, and Ketan Mulmuley 
for their feedback. Special thanks go to Christian Krattenthaler for his detailed comments 
on the manuscript. I am grateful to the Simons Institute for the Theory of Computing 
in Berkeley for making possible the semester program 
``Algorithms and Complexity in Algebraic Geometry'', 
that provided ideal conditions for achieving the recent progress outlined in this survey.

\def$'${$'$}
\begin{thebibliography}{10}

\bibitem{AT:92}
Noga Alon and Michael Tarsi.
\newblock Colorings and orientations of graphs.
\newblock {\epsilonm Combinatorica}, 12(2):125--134, 1992.

\bibitem{al-bo-ve:15}
Jarod Alper, Tristram Bogart, and Mauricio Velasco.
\newblock A lower bound for the determinantal complexity of hypersurface.
\newblock {\epsilonm Found. Comput. Math.}, 2016.
\newblock To appear.

\bibitem{blasiak:12}
Jonah Blasiak.
\newblock Kronecker coefficients for one hook shape.
\newblock arXiv:1209.2018, 2012.

\bibitem{brion:87}
Michel Brion.
\newblock Sur l'image de l'application moment.
\newblock In {\epsilonm S\'eminaire d'alg\`ebre {P}aul {D}ubreil et {M}arie-{P}aule
  {M}alliavin ({P}aris, 1986)}, volume 1296 of {\epsilonm Lecture Notes in Math.},
  pages 177--192. Springer, Berlin, 1987.

\bibitem{BDLG:00}
Sara Brunetti, Alberto Del~Lungo, and Yan G\'{e}rard.
\newblock On the computational complexity of reconstructing three-dimensional
  lattice sets from their two-dimensional {X}-rays.
\newblock In {\epsilonm Proceedings of the {W}orkshop on {D}iscrete {T}omography:
  {A}lgorithms and {A}pplications ({C}ertosa di {P}ontignano, 2000)}, volume
  339, pages 59--73, 2001.

\bibitem{buer:00-3}
Peter B{\"u}rgisser.
\newblock {\epsilonm Completeness and Reduction in Algebraic Complexity Theory},
  volume~7 of {\epsilonm {A}lgorithms and {C}omputation in {M}athematics}.
\newblock Springer Verlag, 2000.

\bibitem{bci:10}
Peter B\"urgisser, Matthias Christandl, and Christian Ikenmeyer.
\newblock Even partitions in plethysms.
\newblock {\epsilonm Journal of Algebra}, 328(1):322 -- 329, 2011.

\bibitem{buci:09}
Peter B{\"u}rgisser, Matthias Christandl, and Christian Ikenmeyer.
\newblock Nonvanishing of {K}ronecker coefficients for rectangular shapes.
\newblock {\epsilonm Adv. Math.}, 227(5):2082--2091, 2011.

\bibitem{bcmw:15}
Peter B\"urgisser, Matthias Christandl, Ketan Mulmuley, and Michael Walter.
\newblock On the complexity of the membership problem for moment polytopes.
\newblock arXiv:1511.03675, 2015.

\bibitem{BHI:15}
Peter B\"urgisser, Jesko H\"uttenhain, and Christian Ikenmeyer.
\newblock Permanent versus determinant: not via saturations.
\newblock arXiv:1501.05528, 2015.

\bibitem{buik:15}
Peter B\"urgisser and Christian Ikenmeyer.
\newblock Fundamental invariants of orbit closures.
\newblock arXiv:1511.02927, 2015.

\bibitem{bu-ik:13}
Peter B{\"u}rgisser and Christian Ikenmeyer.
\newblock Deciding positivity of {L}ittlewood-{R}ichardson coefficients.
\newblock {\epsilonm SIAM J. Discrete Math.}, 27(4):1639--1681, 2013.

\bibitem{BI:13}
Peter B{\"u}rgisser and Christian Ikenmeyer.
\newblock Explicit lower bounds via geometric complexity theory.
\newblock {\epsilonm Proceedings 45th Annual ACM Symposium on Theory of Computing
  2013}, pages 141--150, 2013.

\bibitem{bu-ik-pa:16}
Peter B\"{u}rgisser, Christian Ikenmeyer, and Greta Panova.
\newblock No occurrence obstructions in geometric complexity theory.
\newblock arXiv:1604.06431, 2016.

\bibitem{BLMW:11}
Peter B\"urgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman.
\newblock An overview of mathematical issues arising in the {G}eometric
  complexity theory approach to {VP} v.s. {VNP}.
\newblock {\epsilonm {SIAM} J. Comput.}, 40(4):1179--1209, 2011.

\bibitem{cai:2010}
Jin-Yi Cai, Xi~Chen, and Dong Li.
\newblock Quadratic lower bound for permanent vs. determinant in any
  characteristic.
\newblock {\epsilonm Comput. Complexity}, 19(1):37--56, 2010.

\bibitem{carre-thibon:92}
Christophe Carr{\'e} and Jean-Yves Thibon.
\newblock Plethysm and vertex operators.
\newblock {\epsilonm Adv. in Appl. Math.}, 13(4):390--403, 1992.

\bibitem{cdw:12}
Matthias Christandl, Brent Doran, and Michael Walter.
\newblock Computing multiplicities of {L}ie group representations.
\newblock In {\epsilonm 2012 {IEEE} 53rd {A}nnual {S}ymposium on {F}oundations of
  {C}omputer {S}cience---{FOCS} 2012}, pages 639--648. IEEE Computer Soc., Los
  Alamitos, CA, 2012.

\bibitem{ChrMit06}
Matthias Christandl and Graeme Mitchison.
\newblock The spectra of density operators and the {K}ronecker coefficients of
  the symmetric group.
\newblock {\epsilonm Comm. Math. Phys.}, 261(3):789--797, February 2006.

\bibitem{ChristHarrowMitch07}
Matthias Christiandl, Aram Harrow, and Graeme Mitchison.
\newblock On nonzero {K}ronecker coefficients and what they tell us about
  spectra.
\newblock {\epsilonm Comm. Math. Phys.}, 270(3):575--585, 2007.

\bibitem{dieu:49}
Jean Dieudonn{\'e}.
\newblock Sur une g\'en\'eralisation du groupe orthogonal \`a quatre variables.
\newblock {\epsilonm Arch. Math.}, 1:282--287, 1949.

\bibitem{draisma-siam:15}
Jan Draisma.
\newblock Geometry, invariants, and the elusive search for complexity lower
  bounds.
\newblock {\epsilonm SIAM News}, 48(6), 2015.

\bibitem{Dri:98}
Arthur~A. Drisko.
\newblock Proof of the {A}lon-{T}arsi conjecture for {$n=2^rp$}.
\newblock {\epsilonm Electron. J. Combin.}, 5:Research paper 28, 5 pp. (electronic),
  1998.

\bibitem{Frobdet}
Georg Frobenius.
\newblock {\"U}ber die {D}arstellung der endlichen {G}ruppen durch lineare
  {S}ubstitutionen.
\newblock {\epsilonm Sitzungsber Deutsch. Akad. Wiss. Berlin}, pages 994--1015, 1897.

\bibitem{FH:91}
William Fulton and Joe Harris.
\newblock {\epsilonm Representation Theory - A First Course}, volume 129 of {\epsilonm
  Graduate Texts in Mathematics}.
\newblock Springer, 1991.

\bibitem{Gly:10}
David~G. Glynn.
\newblock The conjectures of {A}lon-{T}arsi and {R}ota in dimension prime minus
  one.
\newblock {\epsilonm SIAM J. Discrete Math.}, 24(2):394--399, 2010.

\bibitem{grenet:11}
Bruno Grenet.
\newblock An upper bound for the permanent versus determinant problem.
\newblock Accepted for {\it Theory of Computing}, 2011.

\bibitem{lahu:16}
Jesko H{\"u}ttenhain and Pierre Lairez.
\newblock The boundary of the orbit of the 3 by 3 determinant polynomial.
\newblock arXiv:1512.02437, 2015.

\bibitem{ike:12b}
Christian Ikenmeyer.
\newblock {\epsilonm Geometric Complexity Theory, Tensor Rank, and
  {L}ittlewood-{R}ichardson Coefficients}.
\newblock PhD thesis, Institute of Mathematics, University of Paderborn, 2012.

\bibitem{hu-ik:14}
Christian Ikenmeyer and Jesko H\"{u}ttenhain.
\newblock Binary determinantal complexity.
\newblock {\epsilonm Linear Algebra and its Applications}, 504:559--573, 2016.

\bibitem{ik-m-w:15}
Christian Ikenmeyer, Ketan Mulmuley, and Michael Walter.
\newblock On vanishing of {K}ronecker coefficients.
\newblock arXiv:1507.02955, 2015.

\bibitem{ik-pa:15}
Christian Ikenmeyer and Greta Panova.
\newblock Rectangular {K}ronecker coefficients and plethysms in geometric
  complexity theory.
\newblock arXiv:1512.03798, 2015.

\bibitem{kadish-landsberg:14}
Harlan Kadish and J.~M. Landsberg.
\newblock Padded polynomials, their cousins, and geometric complexity theory.
\newblock {\epsilonm Comm. Algebra}, 42(5):2171--2180, 2014.

\bibitem{klya:04}
Alexander Klyachko.
\newblock Quantum marginal problem and representations of the symmetric group.
\newblock arXiv:quant-ph/0409113, 2003.

\bibitem{kraf:84}
Hanspeter Kraft.
\newblock {\epsilonm Geometrische {M}ethoden in der {I}nvariantentheorie}.
\newblock Aspects of Mathematics, D1. Friedr. Vieweg \& Sohn, Braunschweig,
  1984.

\bibitem{Kum:15}
Shrawan Kumar.
\newblock A study of the representations supported by the orbit closure of the
  determinant.
\newblock {\epsilonm Compositio Mathematica}, 151:292--312, 2 2015.

\bibitem{lare:15}
Joseph Landsberg and Nicolas Ressayre.
\newblock Permanent v.\ determinant: an exponential lower bound assuming
  symmetry and a potential path towards {V}aliant's conjecture.
\newblock arXiv:1508.05788, 2015.

\bibitem{lamare:13}
Joseph~M. Landsberg, Laurent Manivel, and Nicolas Ressayre.
\newblock Hypersurfaces with degenerate duals and the geometric complexity
  theory program.
\newblock {\epsilonm Comment. Math. Helv.}, 88(2):469--484, 2013.

\bibitem{lapa:90}
M.~Larsen and R.~Pink.
\newblock Determining representations from invariant dimensions.
\newblock {\epsilonm Invent. math.}, 102:377--389, 1990.

\bibitem{deloera:06}
Jes{\'u}~De Loera and Tyrrell McAllister.
\newblock On the computation of {C}lebsch-{G}ordan coefficients and the
  dilation effect.
\newblock {\epsilonm Experiment. Math.}, 15(1):7--19, 2006.

\bibitem{mapo:08}
Guillaume Malod and Natacha Portier.
\newblock Characterizing {V}aliant's algebraic complexity classes.
\newblock {\epsilonm Journal of Complexity}, 24:16--38, 2008.

\bibitem{mani:98}
L.~Manivel.
\newblock Gaussian maps and plethysm.
\newblock In {\epsilonm Algebraic geometry ({C}atania, 1993/{B}arcelona, 1994)},
  volume 200 of {\epsilonm Lecture Notes in Pure and Appl. Math.}, pages 91--117.
  Dekker, New York, 1998.

\bibitem{mani:97}
Laurent Manivel.
\newblock Applications de {G}auss et pl\'ethysme.
\newblock {\epsilonm Ann. Inst. Fourier (Grenoble)}, 47(3):715--773, 1997.

\bibitem{marcus-minc:61}
Marvin Marcus and Henryk Minc.
\newblock On the relation between the determinant and the permanent.
\newblock {\epsilonm Illinois J. Math.}, 5:376--381, 1961.

\bibitem{mignon-ressayre:04}
Thierry Mignon and Nicolas Ressayre.
\newblock A quadratic bound for the determinant and permanent problem.
\newblock {\epsilonm Int. Math. Res. Not.}, 79:4241--4253, 2004.

\bibitem{gct6}
Ketan~D. Mulmuley.
\newblock Geometric complexity theory {VI}: the flip via positivity.
\newblock Technical report, Computer Science Department, the University of
  Chicago, 2010.

\bibitem{gct3}
Ketan~D. Mulmuley, Hariharan Narayanan, and Milind Sohoni.
\newblock Geometric complexity theory {III}: on deciding nonvanishing of a
  {L}ittlewood-{R}ichardson coefficient.
\newblock {\epsilonm J. Algebraic Combin.}, 36(1):103--110, 2012.

\bibitem{gct1}
Ketan~D. Mulmuley and Milind Sohoni.
\newblock Geometric complexity theory. {I}. {A}n approach to the {P} vs.\ {NP}
  and related problems.
\newblock {\epsilonm SIAM J. Comput.}, 31(2):496--526 (electronic), 2001.

\bibitem{gct2}
Ketan~D. Mulmuley and Milind Sohoni.
\newblock Geometric complexity theory. {II}. {T}owards explicit obstructions
  for embeddings among class varieties.
\newblock {\epsilonm SIAM J. Comput.}, 38(3):1175--1206, 2008.

\bibitem{mumf:95}
David Mumford.
\newblock {\epsilonm Algebraic geometry. {I}}.
\newblock Classics in Mathematics. Springer-Verlag, Berlin, 1995.
\newblock Complex projective varieties, Reprint of the 1976 edition.

\bibitem{ness:84}
Linda Ness.
\newblock A stratification of the null cone via the moment map.
\newblock {\epsilonm Amer. J. Math.}, 106(6):1281--1329, 1984.
\newblock With an appendix by David Mumford.

\bibitem{polya:13}
Georg P{\'o}lya.
\newblock Aufgabe 424.
\newblock {\epsilonm Arch. Math. Phys.}, 20:271, 1913.

\bibitem{procesi:07}
Claudio Procesi.
\newblock {\epsilonm Lie groups}.
\newblock Universitext. Springer, New York, 2007.
\newblock An approach through invariants and representations.

\bibitem{alfonsin:05}
Jorge~Luis Ram{\'{\i}}rez~Alfons{\'{\i}}n.
\newblock {\epsilonm The {D}iophantine {F}robenius problem}, volume~30 of {\epsilonm Oxford
  Lecture Series in Mathematics and its Applications}.
\newblock Oxford University Press, Oxford, 2005.

\bibitem{ressayre:10}
Nicolas Ressayre.
\newblock Geometric invariant theory and the generalized eigenvalue problem.
\newblock {\epsilonm Invent. Math}, 180:389--441, 2010.

\bibitem{schur:68}
Issai Schur.
\newblock {\epsilonm Vorlesungen \"uber {I}nvariantentheorie}.
\newblock Bearbeitet und herausgegeben von Helmut Grunsky. Die Grundlehren der
  mathematischen Wissenschaften, Band 143. Springer-Verlag, Berlin-New York,
  1968.

\bibitem{sturmfels:93}
Bernd Sturmfels.
\newblock {\epsilonm Algorithms in invariant theory}.
\newblock Texts and Monographs in Symbolic Computation. Springer-Verlag,
  Vienna, 1993.

\bibitem{szego:13}
G\'abor Szeg{\H o}.
\newblock Zu {A}ufgabe 424.
\newblock {\epsilonm Arch. Math. Phys.}, 21:291--292, 1913.

\bibitem{Val:79b}
Leslie~G. Valiant.
\newblock Completeness classes in algebra.
\newblock In {\epsilonm Conference {R}ecord of the {E}leventh {A}nnual {ACM}
  {S}ymposium on {T}heory of {C}omputing ({A}tlanta, {G}a., 1979)}, pages
  249--261. ACM, New York, 1979.

\bibitem{vallejo:00}
Ernesto Vallejo.
\newblock Plane partitions and characters of the symmetric group.
\newblock {\epsilonm J. Algebraic Combin.}, 11(1):79--88, 2000.

\bibitem{verwa:14}
Mich{\`e}le Vergne and Michael Walter.
\newblock Inequalities for moment cones of finite-dimensional representations.
\newblock arXiv:1410.8144, 2015.

\bibitem{wei:90}
Steven~H. Weintraub.
\newblock Some observations on plethysms.
\newblock {\epsilonm J. Algebra}, 129(1):103--114, 1990.

\bibitem{yabe:15}
Akihiro Yabe.
\newblock Bi-polynomial rank and determinantal complexity.
\newblock arXiv:1504.00151, 2015.

\epsilonnd{thebibliography}

\epsilonnd{document}