DIMACS TR: 93-21
Depth Reduction for Noncommutative Arithmetic Circuits
Authors: Eric Allender and Jia Jiao
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.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-21.ps
DIMACS Home Page