It is well known which symmetric Boolean functions can be computed by constant depth, polynomial size, unbounded fan-in circuits, i.e., which are contained in the complexity class AC 0 . This result is sharpened. Symmetric Boolean functions in AC 0  can be computed by unbounded fan-in circuits with the following properties. If the optimal depth of AC 0 -circuits is d, the depth is at most d + 2, the number of wires is almost linear, namely n log O(1)  n, and the number of gates is subpolynomial (but superpolylogarithmic), namely 2 O(logδ n)  for some δ < 1
['Johan Håstad', 'Ingo Wegener', 'Norbert Wurm', 'Sang-Zin Yi']
Optimal depth, very small size circuits for symmetric functions in AC 0