TR95-043 Authors: Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay

Publication: 14th September 1995 16:04

Downloads: 903

Keywords:

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the uniform

setting. This also provides a unified proof of the circuit

characterizations of LOGCFL and \#LOGCFL.

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.

Then we consider non-commutative computation, and show that some

depth reduction is possible over the algebra ($\Sigma^*,$ max,

concat), thus establishing that OptLOGCFL is in AC$^1$. This is

the first depth-reduction result for arithmetic circuits over

a noncommutative semiring, and it complements the lower bounds of

\cite{nisan,kosaraju} showing that depth reduction cannot be done

in the general noncommutative setting.

We define new notions called ``short-left-paths'' and ``short-right-

paths'' and we show that these notions provide a characterization of

the classes of arithmetic circuits for which optimal depth-reduction

is possible. This class also can be characterized using the AuxPDA

model.

Finally, we characterize the languages generated by efficient

circuits over the (union, concat) semiring in terms of simple

one-way machines, and we investigate and extend earlier lower

bounds on non-commutative circuits.