Impossibility results for weak threshold networks

Abstract

It is shown that a weak threshold network (in particular, threshold network) of width w and depth d cannot be constructed from balancers of width p0, p1, . . . , pm-1, if w does not divide Pd, where P is the least common multiple of p0, p1, . . . , pm-1. This holds regardless of the size of the network, as long as it is finite, and it implies a lower bound of logp w on its depth. More strongly, a lower bound of logpmax w is shown on the length of every path from an input wire to any output wire that exhibits the threshold property, where pmax is the maximum among p0, p1, . . . , Pm-1. © 1997 Elsevier Science B.V.