Better bounds for threshold formulas

The computation of threshold functions using formulas over the basis {AND, OR, NOT} is considered. It is shown that every monotone formula that computes the threshold function Tkn/2<k<n2, has size Ω(nk log (n/(k-1))). The same lower bound is shown to hold even in the stronger monotone contact networks model. Nearly optimal bounds on the size of ΣΠΣ formulas computing Tkn for small k are also shown