Depth Reduction for Noncommutative Arithmetic Circuits (Extended Abstract)

Abstract:

We show that for every family of arithmetic circuits of polynomial
size and degree over the algebra ($Sigma^*,$ max, concat), there
is an equivalent family of arithmetic circuits of depth $log^2 n$.
(The depth can be reduced to $log n$ if unbounded fan-in is allowed.)
This is the first depth-reduction result for arithmetic circuits over
a noncommutative semiring, and it complements the lower bounds of
[nisan] and [kosaraju] showing that depth reduction cannot be done
in the general noncommutative setting. The (max,concat) semiring
is of interest, because it characterizes certain classes of
optimization problems. In particular, our results
show that OptSAC$^1$ is contained in AC$^1$.
We also prove other results relating Boolean and arithmetic circuit
complexity. We show that AC$^1$ has no more power than arithmetic
circuits of polynomial size and degree $n^{O(log log n)}$ (improving
the trivial bound of $n^{O(log n)}$). Connections are drawn between
TC$^1$ and arithmetic circuits of polynomial size and degree.