Communication complexity and data compression

Author

Tamm, Ulrich

Author_Institution

Dept. of Econ., Univ. of Appl. Sci., Bielefeld, Germany

fYear

2013

fDate

10-15 Feb. 2013

Firstpage

1

Lastpage

4

Abstract

A result of Ahlswede and Cai for the 2-party communication complexity of set intersection is generalized to a multiparty model. There are relations to several areas as to the direct-sum conjecture and amortized complexity in computational complexity or interactive communication in information theory as well as to wireless sensor networks and even quantum communication. The aim of the paper is mostly to survey these different applications and to draw the attention of researchers in one area to the results and applications in other areas.

Keywords

communication complexity; data compression; information theory; quantum communication; set theory; wireless sensor networks; 2-party communication complexity; amortized complexity; data compression; direct-sum conjecture; information theory; interactive communication; multiparty model; quantum communication; set intersection; wireless sensor network; Complexity theory; Computer science; Information theory; Protocols; Tensile stress; Vectors; Wireless sensor networks; amortized complexity; communication complexity; functions on direct sums; prefix codes;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory and Applications Workshop (ITA), 2013

Conference_Location

San Diego, CA

Print_ISBN

978-1-4673-4648-1

Type

conf

DOI

10.1109/ITA.2013.6502978

Filename

6502978