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 .