Depth Reduction for Composites

We show that every circuit with AND,OR,NOT, and MODₘ gates, m⁺, of polynomial size and depth d can be reduced to a depth-2, SYM∘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. We also list two among the consequences of our construction. One immediate implication is a near-exponential improvement in the depth, from o(loglog n) to o(log n/loglog n), in Williams' program for NEXP circuit lower bounds. In fact, this pushes William's program to the NC¹ frontier. Another, but nontrivial, implication is the strengthening of this o(log n/loglog n) depth lower bound in the Chattopadhyay--Santhanam interactive compression setting.