COMMUNICATION-SPACE TRADEOFFS FOR UNRESTRICTED PROTOCOLS*

Abstract. This paper introduces communicating branching programs and develops a general technique for demonstrating communication-space tradeoffs for pairs ofcommunicating branching programs. This technique is then used to prove communication-space tradeoffs for any pair ofcommunicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. As an example, any pair of communi-cating Boolean branching programs that computes matrix-vector products over GF(2) requires communication-space product f2 (n2), provided the space used is o(n / log n). These are the first examples of communication-space tradeoffs on a completely general model of communicating processes. Key words, communication complexity, lower bound, tradeoff, branching program, universal family of hash functions AMS subject classifications. 68Q05, 68Q10, 68Q22, 68Q25 1. Communication and space. The amount of communication required among pro-cessors cooperatively performing a computation is often the dominant factor in determining the efficiency of parallel or distributed systems, in both practical and theoretical terms. In addition, communication complexity has found surprising applications in the complexity o