Vikraman Arvind, Partha Mukhopadhyay

We give a randomized polynomial-time identity test for

noncommutative circuits of polynomial degree based on the isolation

lemma. Using this result, we show that derandomizing the isolation

lemma implies noncommutative circuit size lower bounds. More

precisely, we consider two restricted versions of the isolation

lemma and show that derandomizing each ...
more >>>

Prerona Chatterjee, Pavel Hrubes

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>>