OPTIMAL DEPTH, VERY SMALL-SIZE CIRCUITS FOR SYMMETRICAL FUNCTIONS IN AC(0)

It is well known which symmetric Boolean functions can be computed by constant depth, polynomial size, unbounded fan-in circuits, i.e., whic h are contained in the complexity class AC0. This result is sharpened. Symmetric Boolean functions in AC0 can be computed by unbounded fan-i n circuits with the following properties. If the optimal depth of AC0- circuits is d, the depth is at most d + 2, the number of wires is almo st linear, namely n log(O)(1) n, and the number of gates is subpolynom ial (but superpolylogarithmic), namely 2O(log(delta) n) for some delta < 1. (C) 1994 Academic Press, Inc.