Identification and other probabilistic models. Rudolf Ahlswede’s lectures on information theory 6. Edited by Alexander Ahlswede, Ingo Althöfer, Christian Deppe and Ulrich Tamm. (English) Zbl 1477.94005

Ahlswede, Rudolf

Foundations in Signal Processing, Communications and Networking 16. Cham: Springer (ISBN 978-3-030-65070-4/hbk; 978-3-030-65072-8/ebook). xxii, 724 p. (2021).

This thick (724 pages) and heavy (1.4 kg) book is the 6th (last) volume of a posthumous tribute by his disciples to Rudolf Ahlswede (died in 2010) – a compilation of series of his lectures on information and coding theory. In this volume “Lectures on information theory 6” the main topic is introduced in 1989 by R. Ahlswede and his post-graduate student Gunter Dueck [R. Ahlswede and G. Dueck, IEEE Trans. Inf. Theory 35, No. 1, 15–29 (1989; Zbl 0671.94007)], Theory of Identification – a communication model, which essentially differs from the Shannon’s information transmission theory. In Shannon’s scheme receiver is decoding every received message, but in modern mass-communication and often broadcasting-based world (the post-Shannon communication) receiver may be interested only in some particular message (both sender and receiver know the set of possible messages) and wants (only) to identify a message in order to decide whether it is of interest for him; codes introduced in Ahlswede-Dueck scheme message’s identification make this possible. In the first part of the book, an overview of classical theory of information transfer is given, the identification theory introduced and several sub-cases considered: identification in the presence of feedback, identification via multi-way channels with feedback, identification via channels with noisy feedback etc. Ahlswede and Dueck found, that the capacity of identification in a noisy channel in their scheme is strongly related to Shannon’s channel capacity \(C\): Shannon proved that with the growth of the message’s length \(n\) the receiver can reliably decode \({2^{nC}}\) messages; in the identification scheme, the limit is doubly exponential: \({2^{{2^{nC}}}}\) but the channel capacity \(C\) remains the same. Intrigued by this similarity Ahlswede started to develop a general theory of information transfer, where several post-Shannon communication formats (channels) are considered and which includes Shannon’s theory of information transmission and the theory of identification in the presence of noise as sub-cases.
The following parts of the book, Part II: “A general theory of identification transfer”, III: “Identificaion, mystery numbers, or common randomness”, IV: “Identification for sources, identification entropy, and hypothesis testing”, V: “Identification and statistics” consider various aspects of the identification theory. Part VI “Recent results” is an overview by book compilers of the results obtained in up to year 2020 – identification against eavesdropping, quantum channnels, identification and secure computation, applications to the Internet of Things etc. In the supplement, Alexander Ahlswede (son) and Gunter Dueck share their memories of Rudolf Ahlswede (“Doch tragen die Schatten noch Bilder…” (p. 715) and recall, how the whole Identification Theory got started: when R. Ahlswede noticed in 1985 the conference paper by J. JáJá [“Identification is easier than decoding”, in: Proceedings of the 26th annual symposium on foundations of computer science. Portland, OR, USA, October 21–23, 1985. Washington, DC: IEEE Computer Society. 43–50 (1985; doi:10.1109/SFCS.1985.32)], he showed the paper to his postgradueate student G. Dueck noticing “this seems very important somehow! It is worth to take a look !” (p. 709) and soon they together produced several papers on the new identificarion theory. The text is well organized and the book is easy to read and should be suitable for graduate students in mathematics, in theoretical computer science, physics and electrical engineering with basic knowledge in probability theory.

Reviewer: Jaak Henno (Tallinn)

MSC:

94-02	Research exposition (monographs, survey articles) pertaining to information and communication theory
94A05	Communication theory
94A15	Information theory (general)
94A17	Measures of information, entropy
94A40	Channel models (including quantum) in information and communication theory
94A60	Cryptography

Keywords:

information theory; coding theory; post-Shannon communication; message identification; general theory of information transfer; channels; channel capacity; probability distributions; entropy; hypotheses testing; probabilistic algorithms; security

Citations:

Zbl 1293.94001; Zbl 1307.94001; Zbl 1406.94001; Zbl 1397.94002; Zbl 1434.94001; Zbl 0671.94007