Depth Reduction for Noncommutative Arithmetic Circuits (Extended Abstract)
Report ID: TR-417-93Author: Jiao, Jia / Allender, Eric
Date: 1993-03-00
Pages: 8
Download Formats: |Postscript|
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.