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