Function-algebraic characterizations of log and polylog parallel time

The main results of this paper are recursion-theoretic characterizations of two parallel complexity classes: the functions computable by uniform bounded fan-in circuit families of log and polylog depth (or equivalently, the functions bitwise computable by alternating Turing machines in log and polylog time). The present characterizations avoid the complex base functions, function constructors, anda priori size or depth bounds typical of previous work on these classes. This simplicity is achieved by extending the tiered recursion techniques of Leivant and Bellantoni & Cook.