Better lower bounds for monotone threshold formulas

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