An artificial neural network (ANN) is commonly modeled by a threshold
circuit, a network of interconnected processing units called linear th
reshold gates. The depth of a circuit represents the number of unit de
lays or the time for parallel computation. The size of a circuit is th
e number of gates and measures the amount of hardware. It was known th
at traditional logic circuits consisting of only unbounded fanin AND,
OR, NOT gates would require at least OMEGA(log n/log log n) depth to c
ompute common arithmetic functions such as the product or the quotient
of two n-bit numbers, if the circuit size is polynomially bounded (in
n). It is shown that ANN's can be much more powerful than traditional
logic circuits, assuming that each threshold gate can be built with a
cost that is comparable to that of AND/OR logic gates. In particular,
the main results show that powering and division can be computed by p
olynomial-size ANN's of depth 4, and multiple product can be computed
by polynomial-size ANN's of depth 5. Moreover, using the techniques de
veloped here, a previous result can be improved by showing that the so
rting of n n-bit numbers can be carried out in a depth-3 polynomial si
ze ANN. Furthermore, it is shown that the sorting network is optimal i
n depth.