The dynamic parallel complexity of computational circuits

We establish connections between parallel circuit evaluation and uniform al gebraic closure properties of unary function classes. We use this connectio n in the development of time-efficient and processor-efficient parallel alg orithms for the evaluation of algebraic circuits. Our algorithm provides a nontrivial upper bound on the parallel complexity of the circuit value prob lem over {R, min, max, +} and {R+, min, max, x}. We partially answer an ope n question of Miller, Ramachandran, and Kaltofen by showing that circuits o ver a polynomial-bounded noncommutative semiring and circuits over infinite noncommutative semirings with a polynomial-bounded dimension over a commut ative semiring can be evaluated in polylogarithmic time in their size and d egree using a polynomial number of processors. We also present an improved parallel algorithm for Boolean circuits.