𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A lower bound for monotone perceptrons

✍ Scribed by F. Green

Publisher
Springer
Year
1995
Tongue
English
Weight
802 KB
Volume
28
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Lower bounds for monotone span programs
Lower bounds for monotone span programs
✍ Amos Beimel; Anna GΓ‘l; Mike Paterson πŸ“‚ Article πŸ“… 1996 πŸ› Springer 🌐 English βš– 900 KB
A Lower Bound for Perceptrons and an Ora
A Lower Bound for Perceptrons and an Oracle Separation of the PPPHHierarchy
✍ Christer Berg; Staffan Ulfberg πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 397 KB

We show that there are functions computable by linear size boolean circuits of depth k that require superpolynomial size perceptrons of depth k&1, for k<log nΓ‚(6 log log n). This result implies the existence of an oracle A such that 7 p, A k 3 PP 7 p, A k & 2 and, in particular, this oracle separate

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.