We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating NEX P from non-uniform AC C .

In particular, we show that every circuit with AND O R N O T , and MO D m gates, m Z + , of polynomial size and depth d can be reduced to a depth- 2 , SY M A N D , 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 ) 2 O ( 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 AC C circuit lower bounds against NEX P . This is just short of O ( log n log log n ) and thus pushes William's program to the N C 1 barrier, since N C 1 is contained in AC C of depth O ( log n log log n ) . A second, but non-immediate, implication regards the strengthening of the AC C lower bound in the Chattopadhyay-Santhanam interactive compression setting.