Two-Way Communication Complexity of Sum-Type Functions For One Processor to Be Informed

The asymmetric two-way communication complexity of a function is a measure of the minimal amount of information required to be communicated between two parties in order for one of them to compute the value of the function at the inputs supplied by the parties. We provide rather sharp lower bounds for this quantity in terms of the rank of a certain matrix transform of the function. For several sum-type functions, such as the Hamming, Lee, or Taxi metrics, they are even tight. We emphasize that for this class of functions the familiar log rank of the function tables gives, in general, a poor lower bound.