McCoy Presentation for:

W. Szpankowski

Department of Computer Science

Purdue University USA

March 22, 2011

NSF CSoI

Purdue, 2011

MCCoy 2011

Outline

1. Szpankowski’s McCoy Nomination Overview

2. Shannon Information Theory

3. Szpankowski’s Technical Contributions • Entropy of Hidden Markov Process

• Constrained Channel Capacity

4. Szpankowski’s Vision: Science of Information • What is Information?

• Post Shannon Information Theory

• NSF Science and Technology Center

Szpankowsk’s McCoy Nomination Overview

McCoy Nomination of Szpankowski for:

• Recently resolved long-standing open problems: the entropy of hidden Markov processes and the noisy constrained capacity.

• For for developing innovative analytic methods for Shannon information theory leading to solutions of several open problems (e.g., Ziv’s

conjecture, Wyner-Ziv conjecture, Steinberg-Gutman conjecture, Huffman’s code redundancy, Csiszár-Shields renewal process redundancy )

• Visionary ideas that led first to the creation of a subfield called “analytic information theory,” then to broadening Shannon Information Theory to a new science of information, and finally to establishing the state of Indiana’s first NSF Science of Technology Center for Science of Information (CSoI).

This nomination is based on the following recent technical results:

[1] P. Jacquet, G. Seroussi and W. Szpankowski, On the Entropy of a Hidden Markov Process, Theoretical Computer Science, 395, 203-219, 2008.

[2] J. Konorski and W. Szpankowski, What is Information? Festschrift in Honor of Jorma Rissanen, 154-172, 2008.

[3] P. Jacquet and W. Szpankowski, Noisy Constrained Capacity for BSC, IEEE Transaction on Information Theory, 56, 5412- 5423, 2010.

Outline Update

1. Szpankowski’s McCoy Nomination Overview

2. Shannon Information Theory

3. Szpankowski’s Technical Contributions

4. Szpankowski’s Vision: Science of Information

Three Theorems of Shannon

Theorem 1 & 3. [Shannon 1948; Lossless & Lossy Data Compression]

compression bit rate ≥ source entropy H(X); for distortion level D: lossy bit rate ≥ rate distortion function R(D).

Theorem 2. [Shannon 1948; Channel Coding ] In Shannon’s words:

It is possible to send information at the capacity through the channel with as small a frequency of errors as desired by proper (long) encoding. This statement is not true for any rate greater than the capacity.