The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.

Stephen Ponzio Jaikumar Radhakrishnan Srinivasan Venkatesh

Published in: STOC (1999)

Keyphrases

mutual information
computational complexity
worst case
decision trees
information theoretic
decision problems
information exchange
human computer
communication protocol