On interactive communication

Ahlswede R, Cai N, Zhang Z (1997)
In: IEEE Transactions on Information Theory. IEEE TRANSACTIONS ON INFORMATION THEORY, 43(1). IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC: 22-37.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Ahlswede, RudolfUniBi; Cai, Ning; Zhang, Zhen
Abstract / Bemerkung
Almost two decades ago Ahlswede introduced an abstract correlated source (V x W, S) with outputs (v, w) is an element of S subset of v x W, where persons P-V and P-W observe v and w, respectively. More recently, Orlitsky considered the minimal number C-m of bits to be transmitted in m rounds to ''inform P-W about v over one channel.'' He showed that C-2 less than or equal to 4C(infinity)+3 and that in general C-2 not similar to C-infinity. We give a simple example for C-3 not similar to C-infinity. However, for the new model ''inform Pw over two channels,'' four rounds are optimal for this example-a result we conjecture in general. If both P-V and P-W are to be informed over two channels about the other outcome, we determine asymptotically the complexities for all sources. In our last model ''inform P-V and P-W over one channel'' for all sources the total number T-2 of required bits is known asymptotically and T-infinity is bounded from below in terms of average degrees. There are exact results for several classes of regular sources. An attempt is made to discuss the methods of the subject systematically.
Stichworte
hypergraph covering and; coloring; worst case complexity; average degree bound; communication complexity; abstract sources
Erscheinungsjahr
1997
Titel des Konferenzbandes
IEEE Transactions on Information Theory
Band
43
Ausgabe
1
Seite(n)
22-37
ISSN
0018-9448
Page URI
https://pub.uni-bielefeld.de/record/1628232

Zitieren

Ahlswede R, Cai N, Zhang Z. On interactive communication. In: IEEE Transactions on Information Theory. IEEE TRANSACTIONS ON INFORMATION THEORY. Vol 43. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC; 1997: 22-37.
Ahlswede, R., Cai, N., & Zhang, Z. (1997). On interactive communication. IEEE Transactions on Information Theory, IEEE TRANSACTIONS ON INFORMATION THEORY, 43, 22-37. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. doi:10.1109/18.567643
Ahlswede, R., Cai, N., and Zhang, Z. (1997). “On interactive communication” in IEEE Transactions on Information Theory IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 43, (IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC), 22-37.
Ahlswede, R., Cai, N., & Zhang, Z., 1997. On interactive communication. In IEEE Transactions on Information Theory. IEEE TRANSACTIONS ON INFORMATION THEORY. no.43 IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, pp. 22-37.
R. Ahlswede, N. Cai, and Z. Zhang, “On interactive communication”, IEEE Transactions on Information Theory, IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 43, IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 1997, pp.22-37.
Ahlswede, R., Cai, N., Zhang, Z.: On interactive communication. IEEE Transactions on Information Theory. IEEE TRANSACTIONS ON INFORMATION THEORY. 43, p. 22-37. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC (1997).
Ahlswede, Rudolf, Cai, Ning, and Zhang, Zhen. “On interactive communication”. IEEE Transactions on Information Theory. IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 1997.Vol. 43. IEEE TRANSACTIONS ON INFORMATION THEORY. 22-37.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar