𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Data Structures and Asymmetric Communication Complexity

✍ Scribed by Peter Bro Miltersen; Noam Nisan; Shmuel Safra; Avi Wigderson

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
424 KB
Volume
57
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our round elimination'' lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the ``round reduction'' techniques used in many previous lower bound proofs.

πŸ“œ SIMILAR VOLUMES

On the complexity of categoricity in com
On the complexity of categoricity in computable structures
✍ Walker M. White πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 192 KB

## Abstract We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Ξ ^1^~1~‐complete, while computable categoricity is Ξ ^0^~4~‐hard. (Β© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Minimizing message complexity of partial
Minimizing message complexity of partially replicated data on hypercubes
✍ Humenik, Keith; Matthews, Peter; Stephens, A. B.; Yesha, Yelena πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 663 KB

Within the framework of distributed and parallel computing, we consider partially replicated data on a hypercube. We address the problem of placing copies on the hypercube in order to minimize message complexity. With realistic restrictions on the read/write ratio and the number of copies, we find t