𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the communication complexity of polling

✍ Scribed by Adele A. Rescigno

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

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The Communication Complexity of Pointer
The Communication Complexity of Pointer Chasing
✍ Stephen J. Ponzio; Jaikumar Radhakrishnan; S. Venkatesh πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 253 KB

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)

On Data Structures and Asymmetric Commun
On Data Structures and Asymmetric Communication Complexity
✍ Peter Bro Miltersen; Noam Nisan; Shmuel Safra; Avi Wigderson πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 424 KB

In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the

Communication complexity of convex optim
Communication complexity of convex optimization
✍ John N Tsitsiklis; Zhi-Quan Luo πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 692 KB

We consider a situation where each of two processors has access to a different convex functionA, i = 1,2, defined on a common bounded domain. The processors are to exchange a number of binary messages, according to some protocol, until they find a point in the domain at which f, + h is minimized, wi