Probability and Statistical Mechanics in Information Science

3 June 2003 - 20 July 2003

Aims

The period will be characterized by a few long series of basicadvanced lectures on information theory,probability, networks, disordered systems, and a number of intensive weeks with several specialized lectures. The first main aim is to give the opportunity to Ph.D. and Post Doc students to learn advanced subjects and ddress their researches. The second main purpose is to allow researchers from different areas to meet and discuss the frontiers of these subjects.

Research Directions

Coding and communication over noisy channels, relations with disordered systems and belief propagation

Information Theory, as developed by Shannon, is a fundamental theory behind all of Digital Communications. The theory gives a precise statement about the fundamental limitations to reliable communication over noisy channels. One of the crowning achievements of this theory is the Noisy Channel Coding theorem, which defines a quantity called capacity of the channel based on maximization of mutual information between the input and the output of the channel over all input probability distributions. If transmission takes place at a rate below capacity then reliable transmission in a precise sense can take place. Conversely, reliable transmission cannot take place if messages are transmitted at a rate above capacity. The proof of the theorem requires taking a suitable thermodynamic limit (block sizes of the codes going to infinity). Capacity achieving codes have now been designed based on low density parity check codes.

The research period at the Centro E. De Giorgi will focus on recent progresses and future perspectives on the relations between these subjects and other branches of probability theory and statistical mechanics, notably disordered systems, belief propagation, large deviations and concentration inequalities. New heuristic and rigorous results on coding can be obtained using these techniques. Networks: information theory, queuing, relations with percolation, random matrices, spanning trees and random graphs

Today, we live in a networked world and communication takes place in a networked environment with the Internet providing a universal communication environment to which various other networks ( for instance wireless networks) are attached. An Information and Communication Theory in the Shannon's sense, suitable for a networked environment, is currently not available but there are promising researches in progress. In recent works on the subject there are suggestions that continuum percolation may be relevant. There is also intense activity on Multi User Information Theory where nested lattice codes may have a role to play. However, in order to emulate Shannon's idea, we have to take a suitable thermodynamic limit and there will not be a universal way of doing this. Moreover, recent work in Probability Theory such as random walks in random environment, stochastic geometry of spanning trees, random matrices and the related free probability theory are likely to play a role in Network Information Theory. The aim of the research period at the Centro De Giorgi is to promote interaction between experts of stochastic networks, queuing theory, information theory, percolation and other subjects of probability and statistical mechanics, with the hope to contribute to the development of a Network Information Theory. Other directions

Many other topics of Information Science relate to probability and statistical mechanics. We intend to touch at least a few questions on quantum computing and other computational ideas related to physics and networks.