An information statistics approach to data stream and communication complexity

Abstract

A new method for proving strong lower bounds in communication complexity is presented. The method is based on the notion of the conditional information complexity of a function which is the amount of information about the inputs that has to be revealed by a communication protocol for the function. For demonstration purposes, the use of the method to derive lower bounds for communication complexity problems arising in the data stream context is discussed.