A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\) (Q798294)

Let \(X_ N=\{x_ 1,x_ 2,...,x_ N\}\) be a set of N Boolean variables. The k-th threshold function over \(X_ N\) (denoted \(T^ N_ k(X_ N))\) is the monotone Boolean function defined to be 1 if and only if at least k of its arguments are 1. In this paper we prove that any monotone Boolean network computing \(T^ N_ 3(X_ N)\) contains at least 2.5N-5.5 gates.