𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bounds for monotone span programs

✍ Scribed by Amos Beimel; Anna Gál; Mike Paterson

Publisher
Springer
Year
1996
Tongue
English
Weight
900 KB
Volume
6
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Better Lower Bounds for Monotone Thresho
Better Lower Bounds for Monotone Threshold Formulas
✍ Jaikumar Radhakrishnan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 670 KB

We show that every monotone formula that computes the threshold function TH k, n , 2 k nÂ2, has size at least wkÂ2x n log(nÂ(k&1)). The same lower bound is shown to hold in the stronger monotone directed contact networks model.