DEPTH REDUCTION FOR CIRCUITS OF UNBOUNDED FAN-IN

We prove that constant depth circuits of size n(log(O(1))n) over the b asis AND, OR, PARITY are no more powerful than circuits of this size w ith depth four. Similar techniques are used to obtain several other de pth reduction theorems; in particular, we show every set in AC0 can be recognized by a family of depth-three threshold circuits of size n(lo g(O(1))n). The size bound n(log(O(1))n) is optimal when considering de pth reduction over AND, OR, and PARITY. Most of our results hold for b oth the uniform and the nonuniform case. (C) 1994 Academic Press, Inc.