Multiparty communication complexity of vector-valued and sum-type functions

Abstract

Rudolf Ahlswede's work on communication complexity dealt with functions defined on direct sums: vector-valued functions and sum-type functions. He was interested in single-letter characterizations and provided several lower bound techniques to this aim. In this paper we shall review these lower bounds and extend them to the "number in hand" multiparty model of communication complexity. © Springer-Verlag Berlin Heidelberg 2013.