𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The bit complexity of the predecessor problem

✍ Scribed by Y. Afek; M. Cohen; E. Haalman

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
348 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

A tight bound of 2n -1 bits on the communication complexity of the "predecessor" problem in a synchronous ring (previously known as the "last in a synchronous ring" problem) is presented. @ 1997 Elsevier Science B.V.

πŸ“œ SIMILAR VOLUMES

Optimal Bounds for the Predecessor Probl
Optimal Bounds for the Predecessor Problem and Related Problems
✍ Paul Beame; Faith E. Fich πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 269 KB

We obtain matching upper and lower bounds for the amount of time to find the predecessor of a given element among the elements of a fixed compactly stored set. Our algorithms are for the unit-cost word RAM with multiplication and are extended to give dynamic algorithms. The lower bounds are proved f

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

The complexity of the network design pro
The complexity of the network design problem
✍ D. S. Johnson; J. K. Lenstra; A. H. G. Rinnooy Kan πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 278 KB