An Introduction to Bisimulation and Coinduction (IBC)

Prof. Davide Sangiorgi
Lab. Focus, Inria (France) and University of Bologna (Italy)

Summary:
A fundamental concern in concurrency theory is establishing when two processes are "the same", i.e., undistinguishable to an external observer interacting with them. This notion, called, behavioural equivalence, is the basis upon which a theory of processes can be developed. In the lectures I will review the main forms of behavioural equivalence. I will devote more time to bisimulation, for its importance and mathematical properties. The discovery of bisimulation has spurred the study of coinduction, today widely used also outside concurrency theory. I will therefore also discuss the general meaning of coinduction, with examples from various computer science fields.

The lectures will refer to the draft text An introduction to Bisimulation and Coinduction by Davide Sangiorgi. This draft is being made available by the author exclusively for the students of this course. Please do not criculate!

Learning Theory: Statistical and Game-Theoretic Foundations (LT)

Prof. Nicolò Cesa-Bianchi
Università degli Studi di Milano (Italy)

Summary:
Machine learning is a discipline concerned with the design of algorithms that can predict future data based on past observations. Machine learning has become a standard tool in applications involving intelligent data analysis (extraction of patterns from data, data categorization and clustering, decision-making, adaptive control) and has been applied to domains such as vision, natural language, biology, web, and others. In the course we explore the double nature, statistical and game-theoretic, of machine learning theoretical foundations. We introduce and investigate a number of basic topics in learning theory, including mistake bounds and risk bounds, empirical risk minimization, online linear optimization, compression bounds, linear learning, overfitting and regularization. The ultimate goal of the course is to provide a sound mathematical framework within which one can answer to questions such as: What is the weakest set of assumptions about the data ensuring the existence of a learning algorithm? How much training data should I provide in order to attain a certain predictive performance?

Prerequisites: probability and statistics, linear algebra, optimization.

Advanced Algorithms for Massive Data Sets (MDS)

Prof. Paolo Ferragina
University of Pisa (Italy)

Summary:
Modern information retrieval and data mining applications for the Web (but not only that!) need to carefully cope with the new algorithmic challenges posed by the processing of large datasets and by the architectural features of the memory hierarchy of current computers. These issues force algorithm designers to address simultaneously data compression (fitting more data in the faster/smaller memory levels) and cache-friendly data access (exploiting the accessing features of memory levels). Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces basic and sophisticated algorithmic solutions aimed at minimizing the use of computational resources like time, space, communication, I/O, energy consumption, etc.. The theoretical investigation will go hand-in-hand with some algorithm-engineering considerations.

Prerequisites: Basic course on Algorithms, basic notions of probability theory.

More information (including reading list and slides) are available at the course site.

Foundations of Advanced Networking (FAN)

Prof. Francesco Lo Presti
University of Rome "Tor Vergata" (Italy)

Summary:
The course covers advanced fundamental design and implementation principles of computer networks. We will first review today Internet architecture and revisit the design and implementation principles of Internet, ATM and telephony networks. We will present different protocol mechanisms/techniques as soft state, signaling, randomization, multiplexing and discuss their role in networking. We will then illustrate router design and architecture and scheduling algorithms. We will then review Intra-Domain and Inter-Domain routing and the BGP protocol and policies. The course will then cover traffic engineering and resources allocation. We will review TCP congestion control and illustrate recent results which show how it can be regarded as distributed network optimization problem. Finally we will consider the role of network measurements. In particular, we will address workload models, traffic and/or topology classification and present network tomographic techniques for the estimation of traffic demand matrices and network characteristics.