𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Depth-size trade-offs for parallel prefix computation

✍ Scribed by Marc Snir

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
723 KB
Volume
7
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Time-Randomness Trade-offs in Parallel C
Time-Randomness Trade-offs in Parallel Computation
✍ Danny Krizanc πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 171 KB

In this paper we study two problems which have a provable gap between their randomized and deterministic complexity; oblivious routing on fixed connection Ε½ . networks and finding the median on a parallel comparison tree PCT . We prove a trade-off between the amount of randomness used by an algorith

Spectral Methods for Matrix Rigidity wit
Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity
✍ Satyanarayana V. Lokam πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 210 KB

The rigidity of a matrix measures the number of entries that must be changed in order to reduce its rank below a certain value. The known lower bounds on the rigidity of explicit matrices are very weak. It is known that stronger lower bounds would have important consequences in complexity theory. We

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