Robust lower bounds for communication and stream computation

ABSTRACT

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models [32,29]. We aim to understand whether the hardness of a communication problem holds for almost every allocation of the input, as opposed to holding for perhaps just a few atypical partitions.

A key application is to the heavily studied data stream model. There is a strong connection between our communication lower bounds and lower bounds in the data stream model that are "robust" to the ordering of the data. That is, we prove lower bounds for when the order of the items in the stream is chosen not adversarially but rather uniformly (or near-uniformly) from the set of all permuations. This random-order data stream model has attracted recent interest, since lower bounds here give stronger evidence for the inherent hardness of streaming problems. Our results include the first random-partition communication lower bounds for problems including multi-party set disjointness and gap-Hamming-distance. Both are tight. We also extend and improve previous results [19,7] for a form of pointer jumping that is relevant to the problem of selection (in particular, median finding). Collectively, these results yield lower bounds for a variety of problems in the random-order data stream model, including estimating the number of distinct elements, approximating frequency moments, and quantile estimation.

REFERENCES

• 1: Farid Ablayev, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Theoretical Computer Science, v.157 n.2, p.139-159, May 5, 1996 [doi>10.1016/0304-3975(95)00157-3]
• 2: Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 4: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 5: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An information statistics approach to data stream and communication complexity, Journal of Computer and System Sciences, v.68 n.4, p.702-732, June 2004 [doi>10.1016/j.jcss.2003.11.006]
• 6: Amit Chakrabarti , Graham Cormode , Andrew McGregor, A near-optimal algorithm for computing the entropy of a stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.328-335, January 07-09, 2007, New Orleans, Louisiana
• 7: Amit Chakrabarti , T. S. Jayram , Mihai Pǎtraşcu, Tight lower bounds for selection in randomly ordered streams, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 20-22, 2008, San Francisco, California
• 8: A. Chakrabarti, S. Khot, and X. Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In IEEE Conference on Computational Complexity, pages 107--117, 2003.
• 9: A. Chakrabarti, Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.270, October 14-17, 2001
• 10: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Frequency Estimation of Internet Packet Streams with Limited Space, Proceedings of the 10th Annual European Symposium on Algorithms, p.348-360, September 17-21, 2002
• 11: J. Edmonds and R. Impagliazzo. Manuscript. Unpublished, 1994.
• 12: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 14: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 15: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 16: S. Guha, P. Indyk, and A. McGregor. Sketching information divergences. In Conference on Learning Theory, pages 424--438, 2007.
• 17: Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142390]
• 18: S. Guha and A. McGregor. A general approach to multi-pass stream lower-bounds. Manuscript, 2007.
• 19: S. Guha and A. McGregor. Lower bounds for quantile estimation in random-order and multi-pass streaming. In International Colloquium on Automata, Languages and Programming, pages 704--715, 2007.
• 20: S. Guha and A. McGregor. Space-efficient sampling. In AISTATS, pages 169--176, 2007.
• 21: Sudipto Guha , Andrew McGregor , Suresh Venkatasubramanian, Streaming and sublinear approximation of entropy and information distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.733-742, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109637]
• 22: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 23: Piotr Indyk , David Woodruff, Tight Lower Bounds for the Distinct Elements Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.283, October 11-14, 2003
• 24: Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060621]
• 25: T. S. Jayram , Ravi Kumar , D. Sivakumar, Two applications of information complexity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780640]
• 26: T. S. Jayram, R. Kumar, and D. Sivakumar. The one-way communication complexity of gap hamming distance. In Manuscript http://www.madalgo.au.dk/img/SumSchoo2007_Lecture%20slides/Bibliograph%y/p14_Jayram_07_Manusc_ghd.pdf, 2007.
• 27: Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece [doi>10.1145/380752.380786]
• 28: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 29: Tak Wah Lam , Walter L. Ruzzo, Results on communication complexity classes, Journal of Computer and System Sciences, v.44 n.2, p.324-342, April 1992 [doi>10.1016/0022-0000(92)90025-E]
• 30: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 31: J. I. Munro and M. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315--323, 1980.
• 32: C. H. Papadimitriou and M. Sipser. Communication complexity. J. Comput. Syst. Sci., 28(2):260--269, 1984.
• 33: P. Pudlák and J. Sgall. An upper bound for a communication game related to time-space tradeoffs. Electronic Colloquium on Computational Complexity (ECCC), 2(10), 1995.
• 34: P. Sen. Lower bounds for predecessor searching in the cell probe model. In IEEE Conference on Computational Complexity, pages 73--83, 2003.
• 35: David Woodruff, Optimal space lower bounds for all frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 36: D. P. Woodruff. Distinct elements is hard even for random streams. Manuscript, 2008.
• 37: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Theory

Keywords:
communication complexity, data streams, lower bounds