Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

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 >>>

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

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 >>>