𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tensor-Rank and Lower Bounds for Arithmetic Formulas

✍ Scribed by Raz, Ran

Book ID
121676561
Publisher
Association for Computing Machinery
Year
2013
Tongue
English
Weight
136 KB
Volume
60
Category
Article
ISSN
0004-5411

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Lower bounds for arithmetic problems
Lower bounds for arithmetic problems
✍ JoΓ£o MeidΓ’nis πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 543 KB
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.