The power symmetric polynomial on $n$ variables of degree $d$ is defined as
$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers
of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by
... more >>>

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>