We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on the communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving (conditional) information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.
Our paradigm leads to two main results:
(1) An improved lower bound for the multi-party set-disjointness problem in the general communication complexity model, and a nearly optimal lower bound in the one-way communication model. As a consequence, we show that for any real k > 2, approximating the k-th frequency moment in the data stream model requires \Omega (n^{1 - {2 \mathord{\left/ {\vphantom {2 k}} \right. \kern-\nulldelimiterspace} k}}) space; this resolves a conjecture of Alon, Matias, and Szegedy [3]. (2) A lower bound for the Lp approximation problem in the general communication model; this solves an open problem of Saks and Sun [23]. As a consequence, we show that for p >2, approximating the Lp norm to within a factor of n^\varepsilon in the data stream model with constant number of passes requires \Omega (n^{1 - 4\varepsilon - {2 \mathord{\left/ {\vphantom {2 p}} \right. \kern-\nulldelimiterspace} p}}) space.
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb