𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Communication Complexity of Pointer Chasing

✍ Scribed by Stephen J. Ponzio; Jaikumar Radhakrishnan; S. Venkatesh

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
253 KB
Volume
62
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity 7, 109 127) showed an upper bound of O(n log (k&1) n) for this problem. We prove a matching lower bound; this improves the lower bound of 0(n) shown by N. Nisan and A. Widgerson (1993, SIAM J. Comput. 22, 211 219), and yields a corresponding improvement in the hierarchy results derived by them and by H. Klauck (1998, in ``Proceeding of the Thirteenth Annual IEEE Conference on Computational Complexity,'' pp. 141 152) for bounded-depth monotone circuits.

We consider the bit version of this problem, and show upper and lower bounds. This implies that there is an abrupt jump in complexity, from linear to superlinear, when the number of rounds is reduced to kΓ‚2 or less. We also consider the s-paths version (originally studied by H. Klauck) and show an upper bound. The lower bounds are based on arguments using entropy. One of the main contributions of this work is a transfer lemma for distributions with high entropy; this should be of independent interest.

πŸ“œ SIMILAR VOLUMES

Coding of pointers in the segregation an
Coding of pointers in the segregation analysis program POINTER
✍ Denis C. Shields; Andrew Collins; Angela Marlow πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 110 KB

To the Editor: We have recently encountered a minor discrepancy between the literature documenting the POINTER program and the program as it is implemented. This program allows the segregation analysis of nuclear families, conditioned upon pointers, who are relatives outside the nuclear family throu

Communication Complexity of Gossiping by
Communication Complexity of Gossiping by Packets
✍ Luisa Gargano; Adele A. Rescigno; Ugo Vaccaro πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 153 KB

This paper considers the problem of gossiping with packets of limited size in a network with a cost function. We show that the problem of determining the minimum cost necessary to perform gossiping among a given set of participants with packets of limited size is NP-hard. We also give an approximate

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm

The Communication Complexity of Enumerat
The Communication Complexity of Enumeration, Elimination, and Selection
✍ Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Tore πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 278 KB

Let k, n Β₯ N and f: {0, 1} n Γ— {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k Β₯ {0, 1} n , Bob has y 1 , ..., y k Β₯ {0, 1} n , and they want to compute municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomize