loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
An Information Statistics Approach to Data Stream and Communication Complexity
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, "An Information Statistics Approach to Data Stream and Communication Complexity," Foundations of Computer Science, IEEE Annual Symposium on, pp. 209, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181944,
author = {Ziv Bar-Yossef and T. S. Jayram and Ravi Kumar and D. Sivakumar},
title = {An Information Statistics Approach to Data Stream and Communication Complexity},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {209},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181944},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - An Information Statistics Approach to Data Stream and Communication Complexity
SN - 0272-5428
SP
EP
A1 - Ziv Bar-Yossef,
A1 - T. S. Jayram,
A1 - Ravi Kumar,
A1 - D. Sivakumar,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Ziv Bar-Yossef, IBM Almaden Research Center
T. S. Jayram, IBM Almaden Research Center
Ravi Kumar, IBM Almaden Research Center
D. Sivakumar, IBM Almaden Research Center

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.

    • Citation:
    Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, "An Information Statistics Approach to Data Stream and Communication Complexity," focs, pp.209, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
    Usage of this product signifies your acceptance of the Terms of Use.