𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A size-depth trade-off for the analog computation of Boolean functions

✍ Scribed by György Turán; Farrokh Vatan

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
399 KB
Volume
59
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The number of Boolean functions computed
The number of Boolean functions computed by formulas of a given size
✍ Petr Savický; Alan R. Woods 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 323 KB 👁 2 views

Estimates are given of the number B n, L of distinct functions computed by propositional formulas of size L in n variables, constructed using only literals and n, k Ž connectives. L is the number of occurrences of variables. L y 1 is the number of binary ns Ž . and ks. B n, L is also the number of f

Tiny families of functions with random p
Tiny families of functions with random properties: A quality-size trade-off for hashing
✍ Oded Goldreich; Avi Wigderson 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

We present three explicit constructions of hash functions, which exhibit a Ž trade-off between the size of the family and hence the number of random bits needed to . Ž . generate a member of the family , and the quality or error parameter of the pseudorandom property it achieves. Unlike previous con