About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 2002
Conference paper
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.