Mathematical Foundations of Complex Networked Information Systems

It is with our deepest sadness that we inform everyone that Ralf Koetter, who was one of the speakers of the school, passed away on February 1, 2009

In the past twenty years we have being witnessing a revolution in information and communication technologies, consisting in an astonishing progress in many di®erent research fields. Consider for instance the innovations not only in the classical fields of wireless communication (design of high performance codes very close to the Shannon limit), computer engineering (parallel computing, computer vision, data mining), bioinformatics (genoma interpretation) and VLSI technologies, but also in new fields which will have a great impact in the future such as wireless sensor networks and smart dust, air traffic control, large scale surveillance systems, unmanned mobile multi-vehicle systems, biological networks interpretation and so on.

All of these problems have a common feature, namely they typically deal with complex systems and aste for the solution of large scale optimization problems requiring a prohibitive amount of computation effort even in low dimension. Moreover, the complexity of such systems requires solutions which need to share robustness and adaptation. In spite of the inherent difficulty of these issues, fundamental contributions have already appeared towards the solution of such problems. All these contributions are based on the exploitation of the common structure that, in many cases, these complex systems exhibit: they are often the result of the interactions of numerous but rather simple entities. The complexity is then a consequence of the interactions architecture described by a network and the solutions can be based on mathematical models which allow to predict how the designed local rules give rise to a global behavior obeying prescribed specifications.

The mathematical tools which are playing a fundamental role in addressing these new scientific issues come mainly from combinatorics, probability theory, and statistical mechanics. The concept of graph plays a prominent role. Besides being the basic model of any communication network, it also appears as a natural model to describe interactions among variables: an instance of this are graphical models in modern coding theory.
Random graphs are, in particular, the right model to describe complex networks (e.g. internet, wireless communication networks, sensor networks). Randomness enter at di®erent levels: as a smart technique to mimic the development of complex networks, as an unavoidable modelling technique of faults or noise in the communication links, or also as a useful technique to find typical codes or algorithms with good properties. For a deep analysis of these random models certain probabilistic techniques play a fundamental role. Among these we can list concentration inequalities, large deviation theory and percolation. In the situation in which we have an aggregation of simple entities and in which the complexity rises from the network of interactions, statistical mechanics becomes a natural approach.

This school will propose an introduction to some of the fundamental scientific issues emerging in these disciplines. Research in this field necessarily has to cope with a double difficulty: the problem of constructing coherent mathematical models su±ciently rich to be able to describe the 'real' complex networks we want to study and, on the other side, simple enough to be amenable for a general mathematical theory. While elegant and complete mathematical results already exist for certain specific problems, it is true that the mathematical theory of complex networks is far from being complete and many fundamental open problems still wait for an answer.

Our school consists of five courses. There will be a course on random graphs (by Prof. Bollobas) which will provide all the probabilistic tools needed to deal with these fundamental objects and will propose a number of di®erent ways to model 'randomness'. It will provide the mathematical tools to be able to rigorously study networks in a variety of different scientific and technological contexts.
Two courses will be devoted to communication networks, in particular to the issues of the transmission of information along a network where there are simultaneously many potential receivers and many potential transmitters. These issues are clearly of fundamental technological importance and, at the same time, they constitute a source of challenging mathematical problems. The course by Prof. Kumar will study the basic information theoretic aspects of wireless communication networks, while the second, by Prof. Koetter will address the issues of constructing a coding theory for such networks.
Other two courses will instead focus on the analysis of distributed algorithms over networks and, more generally, graphical models. Particular emphasis will be on the famous message passing algorithms which have applications in a broad variety of contexts including artificial intelligence, distributed inferential statistics, coding theory, and combinatorial optimization. The course by Prof. Zecchina will focus on the statistical physics interpretation of these algorithms with special attention
to applications in classical combinatorial optimization problems. The course by Prof. Wainwright will instead focus on the probabilistic aspects of message passing algorithms and their relation with the relaxation techniques in optimization theory.