## DIMACS TR: 96-03

## Non-Commutative Arithmetic Circuits:
Depth Reduction and Size Lower Bounds

### Authors: Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay

**
ABSTRACT
**

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 Kosaraju and Nisan 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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-03.ps.gz

DIMACS Home Page