Depth Reduction for Noncommutative Arithmetic Circuits

) Eric Allender Department of Computer Science Princeton University 35 Olden Street Princeton, NJ, 08544-2087 allender@cs.princeton.edu Jia Jiao y Department of Computer Science Rutgers University Hill Center, Busch Campus New Brunswick, NJ, USA 08903 jjiao@paul.rutgers.edu 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 [Ni91, Ko90] 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 [AJ92, Vi91]. In particular, our results show that OptSAC 1 is contained in AC 1 . We also pro..