Depth-reduction for composites

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating NEXP from non-uniform ACC. In particular, we show that every circuit with AND, OR, NOT, and MODm gates, m is an element of Z(+), of polynomial size and depth d can be reduced to a depth-2, SYM circle AND, circuit of size 2((log n)O(d)). This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup 2((log n)2O(d)). Therefore, depth-reduction for composite m matches the size of the Allender-Hertrampf construction for primes from 1989. One immediate implication of depth reduction is an improvement of the depth from o(log log n) to o(log n/log log n), in Williams' program for ACC circuit lower bounds against NEXP. This is just short of O(log n/log log n) and thus pushes William's program to the NC1 barrier, since NC1 is contained in ACC of depth O(log n/log log n). A second, but non-immediate, implication regards the strengthening of the ACC lower bound in the Chattopadhyay-Santhanam interactive compression setting.