Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-417-93

Authors:

Date:

February 1993

Pages:

8

Download Formats:

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.