Radhakrishnan, J. (1991) Better bounds for threshold formulas Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991 . pp. 314-323.
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...
Related URL: http://dx.doi.org/10.1109/SFCS.1991.185384
Abstract
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991. |
| ID Code: | 89533 |
| Deposited On: | 27 Apr 2012 14:16 |
| Last Modified: | 27 Apr 2012 14:16 |
Repository Staff Only: item control page
