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 MOD_m gates, m ε Z⁺, 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. One immediate implication of depth reduction is an improvement of the depth from o(loglog n) to o(log n/loglog n), in Williams' program for ACC circuit lower bounds against NEXP. This is just short of O(log n/loglog n) and thus pushes William's program to the NC¹ barrier, since NC¹ is contained in ACC of depth O(log n/loglog n). A second, but non-immediate, implication regards the strengthening of the ACC lower bound in the Chattopadhyay-Santhanam interactive compression setting.

I. Introduction

The development of computational complexity is vastly a history of conjectures, and gaps between these conjectures and what is actually proved. One such story regards the power of gates in small-depth boolean circuits that also have AND, OR, NOT gates. A gate outputs 1 if and only if the number of Is in its input is a multiple of . What is known for prime stands in sharp contrast to what is known for composite .