The following size-depth tradeoff for threshold circuits is obtained:
any threshold circuit of depth d that computes the parity function on
n variables must have at least n(1+c theta-d) edges, where c > 0 and t
heta less than or equal to 3 are constants independent of n and d. Pre
viously known constructions show that up to the choice of c and a this
bound is best possible. In particular, the lower bound implies an aff
irmative answer to the conjecture of Paturi and Saks that a bounded-de
pth threshold circuit that computes parity requires a superlinear numb
er of edges. This is the first superlinear lower bound for an explicit
function that holds for any fixed depth and the first that applies to
threshold circuits with unrestricted weights. The tradeoff is obtaine
d as a consequence of a general restriction theorem for threshold circ
uits with a small number of edges: For any threshold circuit with n in
puts, depth d, and at most kn edges, there exists a partial assignment
to the inputs that fixes the output of the circuit to a constant whil
e leaving [n/(c(1)k)(c2 theta d)] variables unfixed, where c(1),c(2) >
0 and theta less than or equal to 3 are constants independent of 72,
k, and d. A tradeoff between the number of gates and depth is also pro
ved: any threshold circuit of depth d that computes the parity of n va
riables has at least (n/2)(1/2(d-1)) gates. This tradeoff, which is es
sentially the best possible, was proved previously (with a better cons
tant in the exponent) for the case of threshold circuits with polynomi
ally bounded weights in [K. Siu, V. Roychowdury, and T. Kailath, IEEE
Trans. Inform. Theory, 40 (1994), pp. 455-466]; the result in the pres
ent paper holds for unrestricted weights.