CS 789 THEORY SEMINAR [home]

Speaker:  Ravi Kumar
Affiliation: IBM Almaden
Date: Monday, October 27, 2003
Title: An information statistics approach to communication complexity and data streams

Abstract:

Alice and Bob are given a bit each, and wish to probabilistically compute the AND of their bits by exchanging messages; at the same time they would like the transcript of their messages to reveal as little information about their bits as possible. We formulate questions of this nature precisely, and present a technique to obtain sharp lower bounds on the amount of information that needs to be revealed. The motivation for studying these problems arises from a brand new method that we develop for obtaining communication complexity lower bounds.

The latter have applications for deriving lower bounds for data stream algorithms. Specifically, we show that computing the frequency moments F_k for k > 2 requires polynomial space in the data stream model; this resolves the conjecture of Alon, Matias, and Szegedy (1996). In addition, we show that computing L_p norms to within a factor of n^c requires n^{1 - 4c - 2/p} space in the data stream model; this generalizes a bound of Saks and Sun (2002).

(Joint work with Ziv Bar-Yossef, T.S. Jayram, and D. Sivakumar)