Threshold Circuits of Small Majority-Depth

Abstract

Constant-depth polynomial-size threshold circuits are usually classified according to their total depth. For example, the best known threshold circuits for iterated multiplication and division have depths four and three, respectively. In this paper, the complexity of threshold circuits is investigated from a different point of view: explicit AND, OR gates are allowed in the circuits, and a threshold circuit is said to have majority-depth d if no path traverses more than d threshold gates. It is then shown that iterated multiplication can be computed by polynomial-size threshold circuits of total depth five but of majority-depth three. Circuits of depth four and majority-depth two are obtained for division and powering. These results rely on a careful implementation of iterated addition and Chinese remaindering. In addition, a simple symbolic calculus for composing circuit classes is developed: this notation allows for a concise and elegant presentation of the results.