BISS 2005: Bertinoro International Spring School for Graduate Studies in Computer Science 7-18 March 2005 University of Bologna Residential Center Bertinoro (Forlì), Italy

[ Courses and Lecturers
| Lecture Schedule
| Important Dates
| Location
| How to Reach Bertinoro
| Registration
| Financial Sponsorship
| Organization
| LocalWeather Forecast]

The school will offer 4 courses each consisting of 15 hours of lectures:

• Approximation, Chance and Networks, Prof. Alessandro Panconesi (University of Rome "La Sapienza")
• Machine Learning, Prof. Alessandro Sperduti (University of Padova)
• Decision diagrams and their applications, Prof. Gianfranco Ciardo (University of California at Riverside)
• Strong static typing and advanced functional programming, Dr. Francesco Zappa Nardelli (INRIA Rocquencourt)

The registration fee for the School is 700,00 Euro and includes all local expenses from the evening of 6 March to mid-day on 18 March including all meals and on-site lodging in double-occupancy rooms. Attendance is limited to 50 students and will be allocated on a first-come-first-served basis. All applicants must complete a Registration Form by 7 February 2005 21 February 2005.

Courses and Lecturers

Summary:
The aim of this course is twofold. On the one hand, we want to discuss several algorithmic problems that are relevant in the context of distributed algorithms for networks. This includes "hot" topics such as protocols to set up secure sensor networks, how to ensure connectivity and other good global properties for wireless networks by means of simple local rules, and routing in ad hoc networks. We shall also make a small detour in to the world of information retrieval for the web, discussing web ranking and, if time allows, social networks.

On the other hand, the discussion will allow us to introduce some mathematical and algorithmic ideas of fundamental importance such as Markov chains, the Theory of Approximation Algorithms for NP-hard Problems, Linear Programming Duality, Probabilistic Algorithms, Branching Processes and Concentration of Measure, together with some new interesting ideas such as link analysis. The usefulness of these tools goes far beyond the specific context in which they will be introduced. Finally, in several cases, the theoretical analysis of the various algorithms will be complemented by an empirical analysis of their actual performance.

Summary:
The course will open with an introduction to basic concepts on Machine Learning within the framework of Statistical Learning Theory, and it will continue by presenting the contributions that several fields of Computer Science give to its definition and structure. Specifically, we will discuss the connections with Logic Programming, which give rise to the Inductive Logic Programming field. Fundamental concepts in this area, such as inverse entailment, inverse implication, inverse resolution, and relative least general generalization, will be presented. Contributions from Information Theory, such as the use of entropy, conditional entropy, minimum description length, error correcting codes, will be discussed as well. A brief introduction to Computational Learning Theory will elucidate the links with the areas of Algorithms and Theoretical Computer Science. We will show that concepts from Computational Geometry, such as convex hulls and Voronoi diagrams, are extensively used in Machine Learning. Links with the area of Formal Languages are highlighted by showing how recursive formal languages can be learned. Finally, we will briefly present practical applications of Machine Learning in Bioinformatics, Information Retrieval, Search Engines, Pattern Recognition, and Data Mining.

Suggested prerequisites: basic knowledge of probability, statistics, logic, calculus, discrete mathematics.

Summary:
This course provides an in-depth introduction to the most important classes of decision diagrams and their applications. Using logic verification and Markov modeling as motivating applications, we show how structured representations can greatly reduce the memory and time complexity of the analysis algorithms in these two fields. We start our decision-diagram journey with the very successful data structure called Binary Decision Diagrams, or BDDs, widely used for state-space generation and temporal logic model checking. Then, we consider two extensions: MDDs, where each internal nodes can make non-binary choices, and MTMDDs, where also the choice of terminal nodes is non-binary, and can therefore encode arbitrary vector and matrices. Then, we move to the seemingly distant area of Kronecker algebra, and show how the Kronecker-based encoding of a matrix is instead strongly related to yet another type of decision diagrams, edge-valued MDDs, or EVMDDs. EVMDDs, either additive or multiplicative, can be shown to be even more efficient than MTMDDs and are therefore an excellent candidate when encoding non-boolean functions. Finally, we conclude with the presentation of a general framework that includes and generalizes all the different types of decision diagrams we introduced, and discuss how this is an essential tool for the computer scientist who wants to store and manipulate very large sets and relations, or vector and matrices.

Summary:
Modern, widespread, industry accepted imperative programming languages like Java are finally incorporating many features that were pioneered more than twenty years ago in the ML family of functional programming languages, but there are still a wealth of features present in bleeding-edge functional programming languages like OCaml and Haskell that are waiting to trickle into the real world applications. We will give a modern presentation of the advanced, formal features of moder functional, statically typed programming languages, pointing to the theory underneath each of these features, and hinting at real applications that are being developed right now based on these features. We will start by recalling the basics notions of formal operational semantics, and we will present the modern techniques used today to show that a complex language is type safe (progress and subject reduction). We will then look at the type inference algorithms, nowadays clearly described as constraint collection and resolution systems. We will also briefly discuss the module system and the object system found in the leading statically typed functional programming language OCaml, and point to possible extensions and applications of these theories to the manipulation of XML documents, a quite trendy application field for formal tools.

Lecture Schedule

Important Dates

Location

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access.  From the fortress you can enjoy a beautiful vista that stretches from the Tuscan Apennines to the Adriatic coast.

How to Reach Bertinoro

Financial Sponsorship

Organization

Last updated: 19 December 2004