Radhakrishnan, Jaikumar (1997) Better lower bounds for monotone threshold formulas Journal of Computer and System Sciences, 54 (2). pp. 221-226. ISSN 0022-0000
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1006/jcss.1997.1287
Abstract
We show that every monotone formula that computes the threshold function THk, n, 2≤ , k≤n/2, has size at least ⌊k/2⌋ n log(n/(k−1)). The same lower bound is shown to hold in the stronger monotone directed contact networks model.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 57642 |
| Deposited On: | 29 Aug 2011 08:36 |
| Last Modified: | 29 Aug 2011 08:36 |
Repository Staff Only: item control page
