\documentclass[17pt,dvips,landscape]{foils}

\MyLogo{MCCoy 2011}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage[usenames]{color}
\usepackage{epsfig}
\usepackage[ps2pdf]{hyperref}

\usepackage{texpower}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\newcommand{\zdot}{\bar{z}}
\newcommand{\pbeta}{P_{\beta}}
\newcommand{\Ill}{\mathcal{I}_{\ell_1,\ell_2}}
\newcommand{\Ills}{\mathcal{I}_{\ell_1,\ell_2}^*}
\newcommand{\minp}{{\min{\rule{0mm}{1ex}}\!}_+}
\newcommand{\fakeh}[1]{\rule{0pt}{#1}}

\def\basswidth{2.6in}
\def\gutter{0.4in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}
\renewcommand{\baselinestretch}{1.05}


\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\green}[1]{{\color{OliveGreen} #1}}
\newcommand{\red}[1]{{\color{red} #1}}


\def\noi{\noindent}
\def\la{\langle}
\def\rf{\rangle}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\aa{\alpha}
\def\bb{\beta}
\def\bN{{\bf N}}
\def\dd{\delta}
\def\pr{{\rm Pr}}
\def\l{\ell}
\def\t{\theta}
\def\d{\delta}
\def\eps{\varepsilon}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\wt{\widetilde}
\def\ol{\widehat}
\def\TG{\wt{G}}
\def\TC{\wt{C}}
\def\TX{\wt{X}}
\def\TF{\wt{F}}
\def\TV{\wt{V}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Var{{\bf Var}}
\def\E {{\bf E }}
\def\kk{\kappa}
\def\TH{\widetilde{H}}
\def\th{\widetilde{h}}
\def\la{\langle}
\def\ra{\rangle}
\def\om{\omega}
\def\L{{\cal L}}
\def\I{{\cal I}}
\def\sign{\hbox{\rm sign}}
\def\w{{\cal W}}
\def\W{{\cal W}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\hb{\hat{b}}
\def\MT{{\bf T}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\pstat{{\bf \Pi}}

\def\GG{\Gamma}
\def\mm{\mu}
\def\oo{\omega}
\def\ss{\sigma}
\def\w{{\cal W}}
\def\E{{\bf E}}
\def\roh{\rho _{H}}

\def\lf{\lfloor}
\def\rf{\rfloor}
\def\wt{\widetilde}
\def\ol{\widehat}
\def\diff{{\rm d}}
\def\TG{\wt{G}}
\def\TX{\wt{X}}
\def\TW{\wt{W}}
\def\TV{\wt{V}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\U{{\cal U}}
\def\om{\omega}
\def\Var{{\rm Var}}
\def\kk{\kappa}
\def\D{{\cal D}}
\def\DH{\hat{\D}}
\def\DO{\overline{\D}}
\def\a{\alpha}
\def\TH{\widetilde{H}}
\def\th{\widetilde{h}}
\def\M{{\cal M}}
\def\la{\langle}
\def\ra{\rangle}
\def\1/2{\frac{1}{2}}
\def\Stt{{{\cal S}_\theta}}

\def\lb{\lambda}
\def\MM{{\bf M}}
\def\MP{{\bf P}}
\def\MQ{{\bf Q}}
\def\MA{{\bf A}}
\def\MI{{\bf I}}
\def\bp{{\bf p}}
\def\TZ{\widetilde{Z}}

\newcommand{\Zonen}{Z_1^n}
\newcommand{\zonen}{z_1^n}
\newcommand{\Xonen}{X_1^n}
\newcommand{\eq}[1]{(\ref{#1})}
\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\zzz}{z_1,z_2,z_3}
\newcommand{\zbz}{z_1,\bar{z}_2,z_3}
\newcommand{\pxzzz}{P_X(\zzz)}
\newcommand{\pxzbz}{P_X(\zbz)}
\newcommand{\pxz}{P_X(z_1)}
\newcommand{\bldone}{\mathbf{1}}
\newcommand{\bldonet}{\bldone^t}
\newcommand{\MO}[1]{\MM_{#1}^{(0)}}
\newcommand{\Ml}[1]{\MM_{#1}^{(1)}}
\newcommand{\defined}{\stackrel{\mathrm{def}}{=}}
\newcommand{\brz}{\bar{z}}
\newcommand{\bldD}{\mathbf{D}}
\newcommand{\bldP}{\mathbf{P}}
\newcommand{\bldQ}{\mathbf{Q}}
%\newcommand{\bldpi}{\mbox{\boldmath$\pi$}}
\newcommand{\bldpi}{{\bm\pi}}
\newcommand{\xor}{\oplus}
\newcommand{\seqk}[1]{\{#1\}_{k\geq 1}}
\newcommand{\onen}{\frac{1}{n}}
\newcommand{\pab}[1][ab]{\pi_{#1}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\Diverg}{\mathbb{D}}
\newcommand{\dds}[1][s]{\frac{\partial}{\partial #1}}
\newcommand{\bl}{\mathbf{l}_2}
\newcommand{\br}{\mathbf{r}_2}
\newcommand{\bL}{\mathbf{l}_1}
\newcommand{\bR}{\mathbf{r}_1}

\setlength{\textheight}{8in}
\setlength{\textwidth}{8.5in}
\voffset=-1.125in


\begin{document}

\title{McCoy Presentation for:}



\author{
\red{W. Szpankowski} \\
Department of Computer Science\\
Purdue University\\
USA}

\maketitle

%\vspace{0.5in}

\begin{center}
%\green{\bf NSF CSoI}\\
\vspace{0.12in}
\includegraphics{stc-logo.ps}
%\hspace{0.1in}
%\includegraphics{itlogo2.ps}
\footnotesize\color{OliveGreen}  \hfill
\\
\vspace{0.15in}
%\red{\large Purdue, 2011}
\end{center}


\baselineskip=0.3in

\foilhead{Outline}

\begin{enumerate}

\item \red{Szpankowski's McCoy Nomination Overview}
\\
\item \green{Shannon Information Theory}
\\
\item \blue{Szpankowski's Technical Contributions}

\begin{itemize}
%\item \green{Shannon Information Theory}
\med
\item \red{Entropy of Hidden Markov Process}
\smallskip

\item \red{Constrained Channel Capacity}

\end{itemize}

\medskip

\item \green{Szpankowski's Vision: Science of Information} 
\begin{itemize}

\item \blue{What is Information?}
\smallskip

\item \blue{Post Shannon Information Theory}
\smallskip

\item \blue{NSF Science and Technology Center}
\end{itemize}
\medskip

\item \blue{Quotes from Letter Writers}

\end{enumerate}


%\textnormal{

\foilhead{Szpankowsk's McCoy Nomination Overview}
\parsec
McCoy Nomination of \red{Szpankowski} for:
\begin{itemize}
\item Solving \red{long-standing open problems}: 
the \blue{entropy of hidden Markov processes}
and the \blue{noisy constrained capacity}.

\item For \red{developing innovative analytic
methods} for Shannon information theory leading to solutions of several 
\blue{open problems} (e.g., 
{\small
Ziv's conjecture, Wyner-Ziv conjecture, Steinberg-Gutman conjecture,
Huffman's code redundancy, Csisz\'{a}r-Shields renewal process redundancy
\normalsize}
)


\item \red{Visionary ideas} that led
first to the creation of the field of ``\red{analytic information theory},"
and subsequently to broadening of \green{Shannon Information Theory} to a new
\red{science of information}, leading to the establishment of Indiana's  first 
\blue{NSF Science of Technology Center for Science of Information} (CSoI) and
one of only two centers ever awarded in computing disciplines.

\end{itemize}

\foilhead{Szpankowsk's McCoy Nomination Overview}

This \red{nomination is based on} the following recent technical results:

\small
\noindent
[1]~P. Jacquet, G. Seroussi and \red{W. Szpankowski},
On the Entropy of a Hidden Markov Process,
\blue{\it Theoretical Computer Science}, 395, 203-219, 2008.

\noindent
[2]~J. Konorski and \red{W. Szpankowski},
What is Information?
\blue{\it Festschrift in Honor of Jorma Rissanen}, 154-172, 2008. 

\noindent
[3]~P. Jacquet and \red{W. Szpankowski},
Noisy Constrained Capacity for BSC,
\blue{\it IEEE Transaction on  Information Theory}, 56, 5412- 5423, 2010.
\normalsize

\foilhead{Outstanding Challenges in Computing}

\noindent
The most pressing challenge of our times is the data deluge and
the transformation from data to information, and subsequently to knowledge.

\begin{enumerate}

\item {25.21 billion web pages (2009), over 1 trillion distinct URLs (2008).}
\\
\item {The amount of data in the deep web far exceeds this.}
\\
\item {About 56\% of the text data is in english.}
\\
\item \green {Easy Questions: How much unique data? How much information in text?
Translating this information into actionable form?}
\\
\item \green {Increasingly data is not in the form of text -- social networks,
tweets, scientific data (interactions, geometries, time series), economic
transactions, etc.}
\\
\item \red {Harder Questions: How do we quantify this data, how do we extract
information from these datasets? How do we act on this information?}
\\
\item \red {Really Hard Questions: Information has cause and consequence --
How do we reach beyond information?}
\end{enumerate}

\foilhead{Outstanding Challenges in Computing}

\noindent
These are profound questions and Wojtek is an acknowledged world leader in
quantitative methods addressing these problems.

\begin{itemize}

\item The best researchers from the premier institutions, worldwide, have rallied
around him to define and promote the area {\bf [visibility]}.

\item Wojtek has solved some of the longest standing problems in the area
{\bf [Depth]}.

\item Wojtek's unique contributions transcend computing -- reaching out to
scientific disciplines such as life sciences and physics {\bf [Breadth and Impact]}.

\item He has driven the research agenda of the community at large, through
his tireless contributions in the form of conferences, journals, and
workshops {\bf [Service]}.

\end{itemize}


\foilhead{Three Theorems of Shannon}
\parsec
{\bf {\color{blue} Theorem 1 \& 3}}. [{\bf {\color{OliveGreen} Shannon 1948;
Lossless \& Lossy Data Compression}}]
\parsec
{\color{red}
compression bit rate $~\geq~$ source entropy $H(X)$};\\
for distortion level $D$:
\vspace{-0.8em}
\parsec
{\color{red}
lossy bit rate $~\geq ~$ rate distortion function $R(D)$}.
\parsec
\parsec
{\bf {\color{blue} Theorem 2}}. [{\bf {\color{OliveGreen} Shannon 1948; Channel
Coding}}
]\\
In Shannon's words:\\
$
\begin{array}{l}
\includegraphics[width=1in]{shannon.ps} %[width=1.5in]{jaynes.ps}
\end{array} \begin{array}{l}
\mbox{ It is possible to {\color{blue} send information} at the
{\color{red} capacity} through the channel}\\
\mbox{{\color{blue} with as small a frequency of errors as desired} by proper
({\bf {\color{red} long}}) encoding.} \\
\mbox{This statement is {\color{red} not true} for any rate {\color{blue}
greater than} the capacity.}
\end{array}
$
\parsec
\vspace{-0.1in}
\begin{figure}
\vspace{-0.3in}
\centerline{\psfig{file=sobczak-channel.ps}}%,height=7.0in}}
\vspace{-0.3in}
\end{figure}
%How Shannon \red{proved} these theorems?


\foilhead{Theorem 1: AEP and Typical Sequences}
\parsec
$
%\begin{array}{l}
%\includegraphics[width=4.5in]{sobczak-aep3.ps}
%\end{array} \begin{array}{l}
\mbox{\green{\bf Shannon-McMilan-Breiman}:}\\
\\
\mbox{$-\frac{1}{\red{n}} \log P(X_1^n) \to \blue{H}(X)$} \ \ \ ({\rm pr.})\\
\\
\mbox{$\blue{H}(X)$ is the \blue{entropy rate}.}
%\end{array}
$
\parsec
\blue{\bf Asymptotic Equipartition Property}:
Sequences of length $n$ can be partitioned into
\begin{eqnarray*}
\red{ \rm good~set} && ~ \red{G_n^\eps} \ \ \ \ \ P(w) \sim 2^{-n\blue{H}(X)}, 
\ \ \ \ w\in \red{G_n^\eps} \\
\blue{\rm bad~set}  &&~  \blue{B_n^\eps}  \ \ \ \ \ P(\blue{B_n^\eps})<\eps.
\end{eqnarray*}
Also, $|\red{G_n^\eps}| \sim 2^{\blue{n\blue{H}(X)}}$.

\foilhead{Theorem 2: Shannon Random Coding }
\vspace{-0.3in}
\parsec
$
\begin{array}{l}
\includegraphics[width=5in]{sobczak-capacity.ps}
\end{array} \begin{array}{l}
\mbox{There are $2^{n\blue{H}(X)}$ \red{X-typical} sequences}\\
\\
\mbox{There are $2^{n\blue{H}(Y)}$ \red{Y-typical} sequences}\\
\\
\mbox{There are $2^{n\blue{H}(X,Y)}$ \blue{jointly} \red{X,Y-typical}}\\
\mbox{pair of sequences}
\end{array}
\vspace{-0.6in}
$
\parsec
\green{\bf Decoding Rule}: Declare that \blue{sequence sent} $X$ is the
one that is \red{jointly typical} with the \blue{received sequence} $Y$
\underline{provided} there is \red{unique} $X$. % satisfying this property!
\parsec
The \blue{probability of error} (more than one typical pair is):
$$
\frac{2^{n\blue{H(X,Y)}}}{2^{n(\blue{H(X)}+\blue{H(Y)})}}= 
2^{n(\blue{H(X)}+\blue{H(Y)}-\blue{H(X,Y)})}=
2^{-n\green{I}(X,Y)}.
$$
Since there are $2^{n\red{R}}$ messages 
sent, the \blue{total error probability} is approximately
$$
\red{\min} P({\rm \blue{error}}) \sim 2^{-n(\red{\sup}_{P(X)}
\green{I}(X,Y)-\red{R})} = 2^{-n(\green{C}-\red{R})}, \ \ \ 
\green{C}=\sup_{P(X)} I(X,Y).
$$

%\foilhead{Example: Capacity of BSC}
%
%\begin{figure}
%%\vspace{-0.3in}
%\centerline{\psfig{file=sobczak-bsc.ps}}%,height=7.0in}}
%\end{figure}
%\parsec
%\blue{\bf Capacity}:
%\begin{eqnarray*}
%I(X;Y)&=& H(Y)-H(Y|X)\\
%&=&H(Y)-H(\blue{p})\\
%&\leq & 1-H(\blue{p}).
%\end{eqnarray*}
%The \blue{capacity} is achieved for the \red{uniform} input distribution. Thus
%$$
%\green{C}=1-H(\blue{p}).
%$$ 


\foilhead{[Szpankowsky 2010] Noisy Constrained Channel}

%\begin{figure}
%%\vspace{-0.3in}
%\centerline{\psfig{file=sobczak-constraint1.ps}}%,height=7.0in}}
%\end{figure}
%\parsec
Let {\color{red} $\S$} denote the set of binary {\color{red} constrained 
sequences} of length $n$. Here:
$$
{\color{red} \S_{d,k}}= \{\mbox{{\color{blue} (d,k)}~sequences}\},
$$
i.e., {\color{red} no} sequence contains 
{\color{blue} a run of zeros} \red{shorter than
$d$} or \red{longer than $k$} (applications: DVD, CD, blue-rays, biology). 
%\pause
\parsec
{\bf Sequence $\blue{X}\in \red{\S_{(d,k)}}$ can be represented as a 
\blue{\bf MARKOV PROCESS}}.
%\pause
\parsec
$\green{C}(\red{\S},\eps)$ -- {\color{blue} noisy constrained capacity}
defined as
$$
\green{C}(\red{\S},\eps)= \sup_{X \in \S} I(\blue{X;Y})\\
=\lim_{n\to \infty}
\frac{1}{n} \sup_{\blue{X_1^n} \in \red{\S_n}}
I(\blue{X_1^n, Y_1^n}).
$$
%where the suprema are over all {\color{blue} stationary processes} supported on
%{\color{red} $\S$}. \\
\red{\bf This is/\red{was} an open problem since 1948 Shannon work.}

\foilhead{Entropy of Hidden Markov Process}
\parsec
\blue{\bf Hidden Markov Process}: Since
$$
I(X;Y)=\blue{H}(Y)-\red{H(Y|X)}=\blue{H}(Y)-H(\eps)
$$
($H(\eps)=-\eps\log \eps -(1-\eps)\log(1-\eps)$) we \red{need to find}
$\blue{H}(Y)$.\\
But $\red{Y}$ is a \blue{Hidden Markov Process} (HMP)  since it is 
a \green{noisy version of the Markov Process} $\blue{X}$. 
\parsec
\blue{Entropy} of HMP was first investigated by \blue{Blackwell} in 1956 but no
significant progress since then. \red{Why}?


\begin{theorem}[Jacquet, Seroussi, \& \red{Szpankowski}, 2004]
Consider the HMP $Y$ as defined above. The \red{entropy rate}
\begin{eqnarray*}
H(\red{Y}) &=&
%\lim_{n\to\infty}\E[\,-\onen\log P(\red{Y_1^n})\,]\\
%& =&
\lim_{n\to\infty}\frac{1}{n}
\E[-\log\left( \bp_1 \red{\MM(Y_1,Y_2) \cdots \MM(Y_{n-1},Y_n)}
\bldonet\right)]=\green{\mu(P)}
\end{eqnarray*}
where $\green{\mu(P)}$ is a {\color{blue} top Lyapunov exponent} of 
random matrices {\color{red} $\MM(Y_1,Y_2) \cdots \MM(Y_{n-1},Y_n)$} defined as
$$
{\color{red} \MM(Y_{n-1},Y_{n})}=\left[
\begin{array}{ll}
({\color{blue} 1{-} \eps}) P_{\color{red} X}(Y_n|Y_{n-1}) &
{\color{blue} \eps} P_{\color{red} X}(\bar{Y}_n|Y_{n-1})\\
({\color{blue} 1{-}\eps}) P_{\color{red} X}(Y_n|\bar{Y}_{n-1}) &
{\color{blue} \eps} P_{\color{red} X}(\bar{Y}_n|\bar{Y}_{n-1})
\end{array}
\right].
$$
\end{theorem}

\foilhead{Asymptotic Expansion}
\parsec
We now assume that $P(E_i=1)=\red{\eps \to 0}$ is \blue{small}
(\green{never studied before}).
\parsec
\begin{theorem} [Jacquet and \red{Szpankowski}, 2004, 2007]
Assume {\color{red} $r$th order Markov}.
Then the {\color{red} entropy rate} 
of $Y$ for {\color{blue} small}
{\color{red} $\eps$} is
$$
{\color{red} H(Y)} = H(X)-
{\color{blue}f_0(P)} {\color{red} \eps\log \eps}  +
{\color{blue}f_1(P)} {\color{red} \eps} +o(\eps)
$$
for explicitly computable  {\color{blue}$f_0(P)$} and
{\color{blue}$f_1(P)$}; e.g., 
\begin{eqnarray*}
{\color{blue} f_1(P)} = \sum_{z_1^{2r+1}}
P_X(z_1^{2r+1})\log\frac{P_X(z_1^{2r+1})}
{P_X({\zdot_1^{2r+1}})}
= \Diverg\left(P_X(z_1^{2r+1})||P_X({\color{magenta}\zdot_1^{2r+1}})
\right)\,,
\end{eqnarray*}
where
$\zdot^{2r+1}{=}z_1\ldots z_r\red{\bar{z}_{r+1}}z_{r+2}\ldots z_{2r+1}$.
In the above, 
{\color{blue} $\Diverg$} denotes the 
{\color{blue} Kullback-Liebler divergence}. 
\end{theorem}

\foilhead{Noisy Constrained Capacity}
\parsec
In 2004 \blue{Marcus at al.} stated:\\
``{\it $\ldots$ while calculation of the \blue{noise-free capacity}
of constrained sequences is well known, the computation of the
\red{capacity of a constraint} in the \red{presence of noise} $\ldots$ has been
an \red{unsolved problem in the half-century since Shannon's landmark
paper}} $\ldots$.'' 
\parsec
We just showed that 
$$
{\color{red} H(Y)} = H(P)- 
{\color{blue}f_0(P)} {\color{red} \eps\log \eps}  +
{\color{blue}f_1(P)} {\color{red} \eps} +o(\eps).
$$
\parsec
Let {\color{red} $P^{\max}$} be the {\color{red} maxentropic}
maximizing {\color{blue} $H(P)$}. 
%{\color{blue} continuity argument} we arrive at
Then we prove
$$
{\color{red} C(\S,\eps)}{=}
{\color{OliveGreen} C(\S)}{-}{\color{blue}(1-f_0(P^{\max}))} 
{\color{red} \eps\log \eps}
{+}{\color{blue}(f_1(P^{\max})-1)}
{\color{red} \eps}+ o(\eps)
$$
where {\color{OliveGreen} $C(\S)$}  is the \blue{capacity of noiseless} system
($\red{\eps=0}$)
%\pause
\parsec
\begin{theorem}[Jacquet \& \red{Szpankowski}, 2007]
For {\color{red} $k\leq 2d$}, we have
$$
{\color{red} C(\S,\eps)}{=}
{\color{OliveGreen} C(\S)}+A \cdot {\color{red} \eps} +O(\eps^2\log \eps).
$$
For {\color{red} $k> 2d$}, we shall prove that
$$
{\color{red} C(\S,\eps)}{=}
{\color{OliveGreen} C(\S)}+B \cdot {\color{red} \eps \log \eps } +O(\eps),
$$
where $A$ and $B$ are \blue{explicitly computable constants}.
\end{theorem}



\foilhead{Broader Vision: What is Information?}
\parsec
$
\begin{array}{l}
\includegraphics[width=1in]{weizsacker.ps}
\end{array} \begin{array}{l}
\mbox{{\bf {\color{OliveGreen} C. F. Von Weizs\"{a}cker}}:}\\
\mbox{``{\color{red} Information} is only that which
{\color{blue} produces information}" ({\color{OliveGreen} relativity}).}\\
\mbox{``{\color{red} Information} is only that which
{\color{blue} is understood}'' ({\color{OliveGreen} rationality})}\\
\mbox{``{\color{red} Information} has {\color{blue} no absolute meaning}''.}
\end{array}
$
\parsec
{\bf Informally Speaking}:
A piece of data carries {\bf {\color{OliveGreen} information}}
if it can impact a
{\bf {\color{blue} recipient's ability}} to achieve the
{\bf {\color{blue} objective}} of some
{\bf {\color{blue} activity}} in a given
{\bf {\color{blue} context}} within \blue{limited available resources}.
\parsec
\red{Event-Driven Paradigm}: \blue{Systems, State, Event, Context, Attributes},\
\
\blue{Objective}: Objective function \red{objective}$(R,C)$ maps systems' rule $
R$
and context $C$ in to an objective space.
\parsec
\begin{definition}
The {\bf {\color{OliveGreen} amount of information}}
(in a {\color{blue} faultless scenario})
$\green{I}(E)$ carried by the {\color{blue} event
$E$}
in the {\color{blue} context $C$} as measured for a system with the
{\color{blue} rules of conduct $R$} is
$$
\green{I}_{R,C}(E) ={\bf {\color{blue} cost}}
[{\rm {\color{red} objective}}_R(C({\color{blue} E})),
{\rm {\color{red} objective}}_R(C({\color{blue} E})+{\color{blue} E})]
$$
where the {\bf {\color{blue} cost}} (weight, distance) is a cost function.
%is taken according to the ordering of points in the space of objectives.
\end{definition}

\foilhead{Post-Shannon Challenges}
\parsec
Classical \green{Information Theory} needs a \red{recharge} to meet new
\blue{challenges} of emerging applications in
\red{biology, modern communication, knowledge extraction, economics} and
\red{physics}, $\ldots$ .
\parsec
We need to extend
traditional formalisms for \green{information}  to include
(``\blue{meaning}''):
\parsec
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~\blue{structure}, \blue{time, space}, and \blue{semantics
},
\parsec
and others such as:
\parsec
\blue{dynamic information}, \blue{limited resources}, \blue{complexity},
\blue{physical information}, \blue{representation-invariant
information}, and \blue{cooperation \& dependency}.

%\def\basswidth{1.45in}
%\def\gutter{0.35in}
%\med
%\begin{figure}
%\centerline{
%        \psfig{file=wireless1.ps,width=\basswidth}\hspace*{\gutter}
%\hspace*{\gutter}
%        \psfig{file=prot-str1.ps,width=\basswidth}
%\hspace*{\gutter}
%        \psfig{file=brain3.ps,width=\basswidth}
%\hspace*{\gutter}
%        \psfig{file=nanotubes.ps,width=\basswidth}
%}
%\end{figure}

\foilhead{Structure, Time \& Space, and Semantics}
\vspace{-0.4in}
\parsec
$
\begin{array}{l}
\mbox{\green{\bf Structure}:}\\
\mbox{\blue{Measures} are needed for quantifying}\\
\mbox{\green{information} embodied in \red{structures}}\\
\mbox{{\small (e.g., \blue{material structures}, nanostructures,}}\\
\mbox{{\small biomolecules, gene regulatory networks}}\\
\mbox{{\small protein interaction networks, social networks,}}\\
\mbox{\small{financial transactions).}}\\
\mbox{(\blue{Y. Choi \& W.S., ISIT, 2009.})}
\end{array} \begin{array}{ll}
& \includegraphics[clip,trim=-10 0 0 0,width=4.45in]
{crysandamorphous1.ps}
\end{array}
$
\parsec
$
\begin{array}{l}
\mbox{\green{\bf Time \& Space}:}\\
\mbox{Classical \green{Information Theory} is at its \blue{weakest}}\\
\mbox{in dealing with problems of \red{delay}}\\
\mbox{(e.g., \green{information} \blue{arriving late} maybe}\\
\mbox{\red{useless}  or has \red{less} value).}\\
\mbox{(\blue{P. Jacquet et al., IT 2010.})}
\end{array} \begin{array}{ll}
\includegraphics[angle=90,clip,trim=-10 0 0 0,width=3.4in]{facets-wireless.ps}
\end{array}
$
\parsec
\green{\bf Semantics \& Learnable information}:\\
\blue{Data} driven science focuses on \red{extracting} \green{information}
from data.  How much \green{information} can actually be \red{extracted}
from a given \blue{data repository}?
How much \red{knowledge} is in Google's database?\\
\mbox{(\blue{M. Sudan et al., 2010.})}


\foilhead{Limited Resources, Representation, and Cooperation}
\parsec
$
\begin{array}{l}
\mbox{\green{\bf Limited Computational Resources}:}\\
\mbox{In many scenarios, \green{information}}\\
\mbox{is \red{limited} by available}\\
\mbox{\red{computational resources}} \\
\mbox{(e.g., cell phone, living cell).}\\
\mbox{\small{(\blue{Helman \& Cover, 1970, ``Learning with Limited Memory''}.)}}
\end{array} \begin{array}{ll}
\includegraphics[angle=90,clip,trim=-10 0 0 0,width=3.4in]{facets-integer.ps}
\end{array}
$
\parsec
$
\begin{array}{l}
\mbox{\green{\bf Representation-invariant of information}:}\\
\mbox{How to know whether two \blue{representations}}\\
\mbox{of the same \green{information}} \\
\mbox{are \red{information equivalent}?}
\end{array} \begin{array}{ll}
\includegraphics[angle=90,clip,trim=-10 0 0 0,width=3.4in]{facets-text.ps}
\end{array}
$
\parsec
\green{\bf Cooperation}.
Often subsystems may be in
\blue{conflict} (e.g., denial of service) or in \blue{collusion} (e.g., price
fixing).
How does \red{cooperation} impact \green{information}?
(In wireless networks nodes should \blue{cooperate} in their own
\blue{self-interest}.)\\
(\blue{Cuff, et al. IT, 2010}).

\def\basswidth{1.0in}
\def\gutter{0.3in}


\foilhead{Selected Quotes from Letter-Writers}


\begin{itemize}
\item
``Many of Szpankowski's research works are jewels of discrete mathematics.'' (Flajolet)
\medskip
\item
``I believe that Purdue University, and indeed the worldwide scientific community in the
fields of information theory, communication theory, computation theory, and systems biology,
are fortunate in having a scientist and a leader of his accomplishments and vision..'' (Kumar)
\medskip
\item
``I consider his work on the analysis of Lempel-Ziv compression schemes in information
theory his best. Just for this alone, I would not be surprised to see him capture
one day the Shannon award.'' (Devroye)
\medskip
\item
``.. he has already created a
remarkable intellectual atmosphere where people from different disciplines are coming together
drawn by their interest in various aspects of information science, bringing their own distinct
perspective to the field.'' (Datta on Wojtek's STC Center)
\end{itemize}


\foilhead{Thank You.}











\foilhead{Science of Information}
\parsec
The overarching vision of \green{\bf Science of
Information} is to develop rigorous
principles guiding the \blue{extraction, manipulation, and exchange} of
\green{information}, integrating elements of \blue{space, time, structure}, and
\blue{semantics}.
\parsec
\begin{figure}
\vspace{-0.3in}
\centerline{\psfig{file=
/homes/spa/grants/nsf/stc08/prop/figures/figure.draft10.eps,
width=6.8in,height=5.0in}}
\end{figure}

\foilhead{Institute for Science of Information}
\parsec
In 2008 \red{Szpankowski} launched at Purdue the
\begin{center}
{\bf {\color{OliveGreen} \href{http://isihub.org}{Institute for
Science of Information}}}
\end{center}
and in 2010 \blue{National Science Foundation} established \$25M
\begin{center}
\green{\bf Science and Technology Center}
\end{center}
at \blue{Purdue} to do ccollaborative work with  \blue{Berkeley, MIT,
Princeton, Stanford, UIUC} and \blue{Bryn Mawr} \& \blue{Howard U.}
integrating {\color{red} research and teaching} activities
aimed at investigating the
role of {\bf {\color{OliveGreen} information}} from various viewpoints:
from the \red{fundamental theoretical} underpinnings of
green{information} to the science and engineering
of novel information \blue{substrates, biological pathways, communication
networks, economics}, and \blue{complex social systems}.
\parsec
The specific means and goals for the Center are:
\vspace{-0.1in}
\begin{itemize}
\item develope \green{post-Shannon Information Theory},
\item
\href{http://www.cs.purdue.edu/homes/spa/info.html}{{\color{OliveGreen}
Prestige Science Lecture Series on Information}}
to collectively ponder short and long term goals;

\item
organize \red{meetings} and \red{workshops} (e.g.,
\href{http://komster.net/~msmolenski/venice/index.html}{{\color{OliveGreen}
Information Beyond Shannon}}, Orlando 2005, and Venice 2008).


\item
\red{initiate} similar world-wide centers supporting
\blue{research} on \green{information}.
\end{itemize}

\foilhead{That's It}
\big
%\vspace{1in}
\begin{figure}
\centerline{\psfig{file=thanks.ps}}
\end{figure}



\end{document}
