It has recently been shown that it is possible to add two binary numbers in threshold circuits of depth two with polynomial size. It is shown here that the most significant bit of addition, which is a monotone function, needs exponential size when computed in monotone threshold circuits of depth two. In fact, it is shown that even o(n/log n) negations do not suffice for polynomial size. This is the first example of such a gap for this model.
展开▼
