
The main purpose of this paper is pedagogical.
Despite its importance, all proofs of the correctness of Strassen's famous
1969 algorithm to multiply two 2x2 matrices with only seven multiplications
involve some basisdependent calculations such as explicitly multiplying
specific 2x2 matrices, expanding expressions to cancel terms with opposing
signs, or expanding tensors over the standard basis. This makes the proof
nontrivial to memorize and many presentations of the proof avoid showing all
the details and leave a significant amount of verifications to the reader.
In this note we give a short, selfcontained, basisindependent proof of the
existence of Strassen's algorithm that avoids these types of calculations. We
achieve this by focusing on symmetries and algebraic properties.
Our proof can be seen as a coordinatefree version of the construction of
Clausen from 1988, combined with recent work on the geometry of Strassen's
algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.

The permanent versus determinant conjecture is a major problem in complexity
theory that is equivalent to the separation of the complexity classes VP_{ws}
and VNP. Mulmuley and Sohoni (SIAM J. Comput., 2001) suggested to study a
strengthened version of this conjecture over the complex numbers that amounts
to separating the orbit closures of the determinant and padded permanent
polynomials. In that paper it was also proposed to separate these orbit
closures by exhibiting occurrence obstructions, which are irreducible
representations of GL_{n^2}(C), which occur in one coordinate ring of the orbit
closure, but not in the other. We prove that this approach is impossible.
However, we do not rule out the general approach to the permanent versus
determinant problem via multiplicity obstructions as proposed by Mulmuley and
Sohoni.

The problem of constructing hazardfree Boolean circuits dates back to the
1940s and is an important problem in circuit design. Our main lowerbound
result unconditionally shows the existence of functions whose circuit
complexity is polynomially bounded while every hazardfree implementation is
provably of exponential size. Previous lower bounds on the hazardfree
complexity were only valid for depth 2 circuits. The same proof method yields
that every subcubic implementation of Boolean matrix multiplication must have
hazards.
These results follow from a crucial structural insight: Hazardfree
complexity is a natural generalization of monotone complexity to all (not
necessarily monotone) Boolean functions. Thus, we can apply known monotone
complexity lower bounds to find lower bounds on the hazardfree complexity. We
also lift these methods from the monotone setting to prove exponential
hazardfree complexity lower bounds for nonmonotone functions.
As our main upperbound result we show how to efficiently convert a Boolean
circuit into a boundedbit hazardfree circuit with only a polynomially large
blowup in the number of gates. Previously, the best known method yielded
exponentially large circuits in the worst case, so our algorithm gives an
exponential improvement.
As a side result we establish the NPcompleteness of several hazard detection
problems.

This is the second in a series of papers on rank decompositions of the matrix
multiplication tensor. We present new rank $23$ decompositions for the $3\times
3$ matrix multiplication tensor $M_{\langle 3\rangle}$. All our decompositions
have symmetry groups that include the standard cyclic permutation of factors
but otherwise exhibit a range of behavior. One of them has 11 cubes as summands
and admits an unexpected symmetry group of order 12. We establish basic
information regarding symmetry groups of decompositions and outline two
approaches for finding new rank decompositions of $M_{\langle n\rangle}$ for
larger $n$.

We prove that in the geometric complexity theory program the vanishing of
rectangular Kronecker coefficients cannot be used to prove superpolynomial
determinantal complexity lower bounds for the permanent polynomial.
Moreover, we prove the positivity of rectangular Kronecker coefficients for a
large class of partitions where the side lengths of the rectangle are at least
quadratic in the length of the partition. We also compare rectangular Kronecker
coefficients with their corresponding plethysm coefficients, which leads to a
new lower bound for rectangular Kronecker coefficients. Moreover, we prove that
the saturation of the rectangular Kronecker semigroup is trivial, we show that
the rectangular Kronecker positivity stretching factor is 2 for a long first
row, and we completely classify the positivity of rectangular limit Kronecker
coefficients that were introduced by Manivel in 2011.

Valiant's famous determinant versus permanent problem is the flagship problem
in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008)
introduced geometric complexity theory, an approach to study this and related
problems via algebraic geometry and representation theory. Their approach works
by multiplying the permanent polynomial with a high power of a linear form (a
process called padding) and then comparing the orbit closures of the
determinant and the padded permanent. This padding was recently used heavily to
show nogo results for the method of shifted partial derivatives (Efremenko,
Landsberg, Schenck, Weyman, 2016) and for geometric complexity theory
(Ikenmeyer Panova, FOCS 2016 and B\"urgisser, Ikenmeyer Panova, FOCS 2016).
Following a classical homogenization result of Nisan (STOC 1991) we replace the
determinant in geometric complexity theory with the trace of a variable matrix
power. This gives an equivalent but much cleaner homogeneous formulation of
geometric complexity theory in which the padding is removed. This radically
changes the representation theoretic questions involved to prove complexity
lower bounds. We prove that in this homogeneous formulation there are no orbit
occurrence obstructions that prove even superlinear lower bounds on the
complexity of the permanent. This is the first nogo result in geometric
complexity theory that rules out superlinear lower bounds in some model.
Interestinglyin contrast to the determinantthe trace of a variable matrix
power is not uniquely determined by its stabilizer.

We show that the problem of deciding positivity of Kronecker coefficients is
NPhard. Previously, this problem was conjectured to be in P, just as for the
LittlewoodRichardson coefficients. Our result establishes in a formal way that
Kronecker coefficients are more difficult than LittlewoodRichardson
coefficients, unless P=NP.
We also show that there exists a #Pformula for a particular subclass of
Kronecker coefficients whose positivity is NPhard to decide. This is an
evidence that, despite the hardness of the positivity problem, there may well
exist a positive combinatorial formula for the Kronecker coefficients. Finding
such a formula is a major open problem in representation theory and algebraic
combinatorics.
Finally, we consider the existence of the partition triples $(\lambda, \mu,
\pi)$ such that the Kronecker coefficient $k^\lambda_{\mu, \pi} = 0$ but the
Kronecker coefficient $k^{l \lambda}_{l \mu, l \pi} > 0$ for some integer
$l>1$. Such "holes" are of great interest as they witness the failure of the
saturation property for the Kronecker coefficients, which is still poorly
understood. Using insight from computational complexity theory, we turn our
hardness proof into a positive result: We show that not only do there exist
many such triples, but they can also be found efficiently. Specifically, we
show that, for any $0<\epsilon\leq1$, there exists $0<a<1$ such that, for all
$m$, there exist $\Omega(2^{m^a})$ partition triples $(\lambda,\mu,\mu)$ in the
Kronecker cone such that: (a) the Kronecker coefficient $k^\lambda_{\mu,\mu}$
is zero, (b) the height of $\mu$ is $m$, (c) the height of $\lambda$ is $\le
m^\epsilon$, and (d) $\lambda=\mu \le m^3$. The proof of the last result
illustrates the effectiveness of the explicit proof strategy of GCT.

We define tensors, corresponding to cubic polynomials, which have the same
exponent $\omega$ as the matrix multiplication tensor. In particular, we study
the symmetrized matrix multiplication tensor $sM_n$ defined on an $n\times n$
matrix $A$ by $sM_n(A)=trace(A^3)$. The use of polynomials enables the
introduction of additional techniques from algebraic geometry in the study of
the matrix multiplication exponent $\omega$.

In 1979 Valiant showed that the complexity class VP_e of families with
polynomially bounded formula size is contained in the class VP_s of families
that have algebraic branching programs (ABPs) of polynomially bounded size.
Motivated by the problem of separating these classes we study the topological
closure VP_ebar, i.e. the class of polynomials that can be approximated
arbitrarily closely by polynomials in VP_e. We describe VP_ebar with a
strikingly simple complete polynomial (in characteristic different from 2)
whose recursive definition is similar to the Fibonacci numbers. Further
understanding this polynomial seems to be a promising route to new formula
lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992
BenOr and Cleve showed that formula size is polynomially equivalent to width3
ABP size. We extend their result (in characteristic different from 2) by
showing that approximate formula size is polynomially equivalent to approximate
width2 ABP size. This is surprising because in 2011 Allender and Wang gave
explicit polynomials that cannot be computed by width2 ABPs at all! The
details of our construction lead to the aforementioned characterization of
VP_ebar.
As a natural continuation of this work we prove that the class VNP can be
described as the class of families that admit a hypercube summation of
polynomially bounded dimension over a product of polynomially many affine
linear forms. This gives the first separations of algebraic complexity classes
from their nondeterministic analogs.

This is the first in a series of papers on rank decompositions of the matrix
multiplication tensor. In this paper we: establish general facts about rank
decompositions of tensors, describe potential ways to search for new matrix
multiplication decompositions, give a geometric proof of the theorem of
Burichenko's theorem establishing the symmetry group of Strassen's algorithm,
and present two particularly nice subfamilies in the Strassen family of
decompositions.

We answer a question in [Landsberg, Ressayre, 2015], showing the regular
determinantal complexity of the determinant det_m is O(m^3). We answer
questions in, and generalize results of [Aravind, Joglekar, 2015], showing
there is no rank one determinantal expression for perm_m or det_m when m >= 3.
Finally we state and prove several "folklore" results relating different models
of computation.

We show that the two main reduction notions in arithmetic circuit complexity,
pprojections and creductions, differ in power. We do so by showing
unconditionally that there are polynomials that are VNPcomplete under
creductions but not under pprojections. We also show that the question of
which polynomials are VNPcomplete under which type of reductions depends on
the underlying field.

For several objects of interest in geometric complexity theory, namely for
the determinant, the permanent, the product of variables, the power sum, the
unit tensor, and the matrix multiplication tensor, we introduce and study a
fundamental SLinvariant function that relates the coordinate ring of the orbit
with the coordinate ring of its closure. For the power sums we can write down
this fundamental invariant explicitly in most cases. Our constructions
generalize the two Aronhold invariants on ternary cubics. For the other objects
we identify the invariant function conditional on intriguing combinatorial
problems much like the wellknown AlonTarsi conjecture on Latin squares. We
provide computer calculations in small dimensions for these cases. As a main
tool for our analysis, we determine the stabilizers, and we establish the
polystability of all the mentioned forms and tensors (including the generic
ones).

We translate the main theorem in Tom McKay's paper "On plethysm conjectures
of Stanley and Foulkes" (J. Alg. 319, 2008, pp. 20502071) to the language of
weight spaces and projections onto invariant spaces of tensors, which makes its
proof short and elegant.

The Foulkes conjecture states that the multiplicities in the plethysm
Sym^a(Sym^b V) are at most as large as the multiplicities in the plethysm
Sym^b(Sym^a V) for all a <= b. This conjecture has been known to be true for a
<= 4. The main result of this paper is its verification for a = 5. This is
achieved by performing a combinatorial calculation on a computer and using a
propagation theorem of Tom McKay from 2008.
Moreover, we obtain a complete representation theoretic decomposition of the
vanishing ideal of the 5th Chow variety in degree 5, we show that there are no
degree 5 equations for the 6th Chow variety, and we also find some
representation theoretic degree 6 equations for the 6th Chow variety.

Let Det_n denote the closure of the GL_{n^2}(C)orbit of the determinant
polynomial det_n with respect to linear substitution. The highest weights
(partitions) of irreducible GL_{n^2}(C)representations occurring in the
coordinate ring of Det_n form a finitely generated monoid S(Det_n). We prove
that the saturation of S(Det_n) contains all partitions lambda with length at
most n and size divisible by n. This implies that representation theoretic
obstructions for the permanent versus determinant problem must be holes of the
monoid S(Det_n).

In 2012 Jan Saxl conjectured that all irreducible representations of the
symmetric group occur in the decomposition of the tensor square of the
irreducible representation corresponding to the staircase partition. We make
progress on this conjecture by proving the occurrence of all those irreducibles
which correspond to partitions that are comparable to the staircase partition
in the dominance order. Moreover, we use our result to show the occurrence of
all irreducibles corresponding to hook partitions. This generalizes results by
Pak, Panova, and Vallejo from 2013.

We provide explicit combinatorial formulas for Ottaviani's degree 15
invariant which detects cubics in 5 variables that are sums of 7 cubes. Our
approach is based on the chromatic properties of certain graphs and relies on
computer searches and calculations.

We use algebraic geometry to study matrix rigidity, and more generally, the
complexity of computing a matrixvector product, continuing a study initiated
by Kumar, et. al. We (i) exhibit many nonobvious equations testing for
(border) rigidity, (ii) compute degrees of varieties associated to rigidity,
(iii) describe algebraic varieties associated to families of matrices that are
expected to have superlinear rigidity, and (iv) prove results about the ideals
and degrees of cones that are of interest in their own right.

We prove that for writing the 3 by 3 permanent polynomial as a determinant of
a matrix consisting only of zeros, ones, and variables as entries, a 7 by 7
matrix is required. Our proof is computer based and uses the enumeration of
bipartite graphs. Furthermore, we analyze sequences of polynomials that are
determinants of polynomially sized matrices consisting only of zeros, ones, and
variables. We show that these are exactly the sequences in the complexity class
of constant free polynomially sized (weakly) skew circuits.

We present new methods for determining polynomials in the ideal of the
variety of bilinear maps of border rank at most r. We apply these methods to
several cases including the case r = 6 in the space of bilinear maps C^4 x C^4
> C^4. This space of bilinear maps includes the matrix multiplication operator
M_2 for two by two matrices. We show these newly obtained polynomials do not
vanish on the matrix multiplication operator M_2, which gives a new proof that
the border rank of the multiplication of 2 x 2 matrices is seven. Other
examples are considered along with an explanation of how to implement the
methods.

Starting with Knutson and Tao's hive model (in J. Amer. Math. Soc., 1999) we
characterize the LittlewoodRichardson coefficient $c_{\lambda,\mu}^\nu$ of
given partitions $\lambda,\mu,\nu\in N^n$ as the number of capacity achieving
hive flows on the honeycomb graph. Based on this, we design a polynomial time
algorithm for deciding $c_{\lambda,\mu}^\nu >0$. This algorithm is easy to
state and takes $O(n^3 \log \nu_1)$ arithmetic operations and comparisons. We
further show that the capacity achieving hive flows can be seen as the vertices
of a connected graph, which leads to new structural insights into
LittlewoodRichardson coefficients.

We prove the lower bound R(M_m) \geq 3/2 m^2  2 on the border rank of m x m
matrix multiplication by exhibiting explicit representation theoretic
(occurence) obstructions in the sense of the geometric complexity theory (GCT)
program. While this bound is weaker than the one recently obtained by Landsberg
and Ottaviani, these are the first significant lower bounds obtained within the
GCT program. Behind the proof is the new combinatorial concept of obstruction
designs, which encode highest weight vectors in Sym^d\otimes^3(C^n)^* and
provide new insights into Kronecker coefficients.

We develop structural insights into the LittlewoodRichardson graph, whose
number of vertices equals the LittlewoodRichardson coefficient
c({\lambda},{\mu},{\nu}) for given partitions {\lambda}, {\mu}, and {\nu}. This
graph was first introduced by B\"urgisser and Ikenmeyer in arXiv:1204.2484,
where its connectedness was proved.
Our insights are useful for the design of algorithms for computing the
LittlewoodRichardson coefficient: We design an algorithm for the exact
computation of c({\lambda},{\mu},{\nu}) with running time
O(c({\lambda},{\mu},{\nu})^2 poly(n)), where {\lambda}, {\mu}, and {\nu} are
partitions of length at most n. Moreover, we introduce an algorithm for
deciding whether c({\lambda},{\mu},{\nu}) >= t whose running time is O(t^2
poly(n)). Even the existence of a polynomialtime algorithm for deciding
whether c({\lambda},{\mu},{\nu}) >= 2 is a nontrivial new result on its own.
Our insights also lead to the proof of a conjecture by King, Tollu, and
Toumazet posed in 2004, stating that c({\lambda},{\mu},{\nu}) = 2 implies
c(M{\lambda},M{\mu},M{\nu}) = M + 1 for all M. Here, the stretching of
partitions is defined componentwise.

We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell
d$ there exists $k\ge 1$ such that the tensor square of the irreducible
representation of the symmetric group $S_{k\ell d}$ with respect to the
rectangular partition $(k\ell,...,k\ell)$ contains the irreducible
representation corresponding to the stretched partition
$(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version
of this statement in which the stretching factor $k$ is effectively bounded in
terms of $d$. This investigation is motivated by questions of geometric
complexity theory.