๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An exponential lower bound on the size of algebraic decision trees for Max

โœ Scribed by D. Grigoriev; M. Karpinski; A.C. Yao

Publisher
Springer
Year
1998
Tongue
English
Weight
335 KB
Volume
7
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An Exponential Lower Bound for the Size
An Exponential Lower Bound for the Size of Monotone Real Circuits
โœ Armin Haken; Stephen A. Cook ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed t

A lower bound on the size of a complex g
A lower bound on the size of a complex generated by an antichain
โœ P. Frankl ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 427 KB

A short proof of the following result of Kleitman is given: the total number of sets contained in some member of an antichain of size (i) over the n-set is at least (E) + l --+ (i) for 0 < k G in. An equally short proof of Harper's isoperimetric theorem is provided as well.