The communication complexity of pointer chasing (Q5943092)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The communication complexity of pointer chasing |
scientific article; zbMATH DE number 1642220
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The communication complexity of pointer chasing |
scientific article; zbMATH DE number 1642220 |
Statements
The communication complexity of pointer chasing (English)
0 references
10 July 2002
0 references
The bounded round two-party communication complexity of a particular problem -- the pointer chasing problem -- is studied. First, a nonlinear lower bound is proved that matches the known upper bound for this problem. Then, the bit version of the problem is considered, and upper and lower bounds are shown. Also, a certain generalization of the pointer chasing problem, the so-called \(s\)-pointer game, is considered and its upper bound obtained.
0 references
communication complexity
0 references
lower bound
0 references
upper bound
0 references
pointer chasing problem
0 references
