Abstract
Rudolf Ahlswede’s work on communication complexity dealt with functions defined on direct sums: vector–valued functions and sum–type functions. He was interested in single–letter characterizations and provided several lower bound techniques to this aim. In this paper we shall review these lower bounds and extend them to the “number in hand” multiparty model of communication complexity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ahlswede, R.: On code pairs with specified Hamming distances. Colloquia Math. Soc. J. Bolyai 52, 9–47 (1988)
Ahlswede, R., Mörs, M.: Inequalities for code pairs. European J. Combinatorics 9, 175–188 (1988)
Ahlswede, R., Cai, N.: On communication complexity of vector-valued functions. IEEE Trans. Inf. Theory 40(6), 2062–2067 (1994)
Ahlswede, R., Cai, N.: 2-Way communication complexity of sum-type functions for one processor to be informed. Probl. Inf. Transmission 30(1), 1–10 (1994)
Ahlswede, R., Cai, N., Tamm, U.: Communication complexity in lattices. Appl. Math. Letters 6(6), 53–58 (1993)
Ahlswede, R., Cai, N., Zhang, Z.: A general 4–word–inequality with consequences for 2–Way communication complexity. Advances in Applied Mathematics 10, 75–94 (1989)
Ahlswede, R., Zhang, Z.: Code pairs with specified parity of the Hamming distances. Discr. Math. 188, 1–11 (1998)
Ahlswede, R., El Gamal, A., Pang, K.F.: A two–family extremal problem in Hamming space. Discr. Math. 49, 1–5 (1984)
Alon, N., Matias, M., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137–147 (1999)
Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory. In: Proc. IEEE FOCS, pp. 337–347 (1986)
Chen, L., Chitambar, E., Duan, R., Ji, Z., Winter, A.: Tensor rank and stochastic entaglement catalysis for multipartite pure states. Physical Review Letters 105 (2010)
Draisma, J., Kushilevitz, E., Weinreb, E.: Partition arguments in multiparty communication complexity. Theoretical Computer Science 412, 2611–2622 (2011)
Feder, T., Kushilevitz, E., Naor, M., Nisan, N.: Amortized communication complexity. SIAM J. Comp. 24(4), 736–750 (1995)
Hromkovic, J.: Communication Complexity and Parallel Computing. Springer (1997)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997)
Nisan, N., Wigderson, A.: On rank vs communication complexity. Combinatorica 15(4), 557–566 (1995)
Tamm, U.: Communication complexity of sum-Type functions. PhD thesis, Bielefeld (1991)
Tamm, U.: Still another rank determination of set intersection matrices with an application in communication complexity. Appl. Math. Letters 7, 39–44 (1994)
Tamm, U.: Communication complexity of sum - type functions invariant under translation. Inform. and Computation 116(2), 162–173 (1995)
Tamm, U.: Deterministic communication complexity of set intersection. Discr. Appl. Math. 61, 271–283 (1995)
Tamm, U.: Communication complexity of functions on direct sums. In: Althöfer, I., Cai, N., Dueck, G., Khachatrian, L., Pinsker, M., Sárközy, A., Wegener, I., Zhang, Z. (eds.) Numbers, Information and Complexity, pp. 589–602. Kluwer (2000)
Yao, A.C.: Some complexity questions related to distributive computing. In: Proc. ACM STOC, pp. 209–213 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Tamm, U. (2013). Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions. In: Aydinian, H., Cicalese, F., Deppe, C. (eds) Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science, vol 7777. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36899-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-36899-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36898-1
Online ISBN: 978-3-642-36899-8
eBook Packages: Computer ScienceComputer Science (R0)