Introduction

About the school

Italian Computer Science PhD granting institutions under the auspices of GRIN, organizes an annual school offering three graduate-level courses aimed at first-year PhD students in Computer Science. In addition to introducing students to timely research topics, the school is meant to promote acquaintance and collaboration among young European researchers. The 2017 edition of the School is the 23th in the series.
The school will offer 3 courses each consisting of 13 hours of lectures:

  • Approximation Algorithms
    Prof. Fabrizio Grandoni - Scuola Universitaria professionale della Svizzera italiana (Switzerland)
  • Probabilistic Graphical Models in Intelligent Systems
    Prof. Luigi Portinale - University of Piemonte Orientale (Italy)
  • Kleene algebra with tests and applications to network programming
    Prof. Alexandra Silva, University College London (England)

A final evaluation for each course is possible through a final exam or project as determined by the instructor. The daily schedule admits laboratory and/or working group activities to be organized in addition to the lectures.
The registration fee for the School is 550.00 Euro and includes all local expenses from the evening of 5 March to 10 March afternoon including all meals and on-site lodging in double-occupancy rooms. A reduced registration fee of 300.00 Euro is available for local students which will not use the on-site lodging facilities (it includes local expenses for the lectures, coffee breaks and lunches). It is possible to require one additional night for the students that want to leave on Saturday the 12th. In this case the additional cost is 50 Euros.
Attendance is limited to 50 students and will be allocated on a first-come-first-served basis.

Courses

Approximation Algorithms

Prof. Fabrizio Grandoni, Scuola Universitaria professionale della Svizzera italiana

Abstract: Most optimization problems that we need to solve in practice turn out to be NP-hard. Therefore, there is little hope to find efficient (i.e. worst-case polynomial-time) algorithms to solve them. The goal of approximation algorithms is to compute efficiently a solution to an NP-hard optimization problem whose cost is guaranteed to be within a given factor (approximation ratio) from the optimal cost.
In these lectures we will describe some of the most relevant results and techniques in the area of approximation algorithms. We will consider a few fundamental problems, which appear in several real-world applications, and illustrate some of the most common and powerful techniques in the design and analysis of approximation algorithms. We will also discuss the limits of approximation algorithms, by presenting some approximation lower bounds and inapproximability results.

Slides: link (password provided in the classroom)

Exam:

Probabilistic Graphical Models in Intelligent Systems

Prof. Luigi Portinale, University of Piemonte Orientale

Abstract: The course aims at introducing notions and algorithms for Probabilistic Graphical Models (PGM) in Artificial Intelligence (AI). PGMs are the the main AI formalism for dealing with uncertain knowledge and reasoning; they are grounded on both probability calculus and graph theory and represent an effective tool for the construction of intelligent decision support systems. After a short review of probability calculus and of the interpretation of probability, we will discuss different types of PGMs, namely directed models like Bayesian Belief Networks and undirected models like Random Markov Fields. Both representational and algorithmic issues will be discussed, as well as aspects concerning extensions to dynamic models, sensitivity analysis and learning. Concepts from Bayesian decision theory will be introduced, in order to give a better understanding of the formal framework underlying decision networks and their different versions (classical Influence Diagrams vs LIMID models).
Examples of software tools available for the management of PGMs will be presented, together with applications in the areas of dependability of systems , FDIR (fault detection identification and recovery) and planning under uncertainty.
Course Outline

  • Probability theory: main concepts and interpretation (frequentist vs subjective)
  • Introduction to Probabilistic Graphical Models
    • directed vs undirected models: Bayesian Networks and Markov Random Fields
    • graph theoretic dependency
    • modeling Issues,
    • exact inference
    • approximate inference
    • learning approaches (parameter and structure learning)
    • dynamic models (DBN)
  • Decision Theory
    • rationality axioms
    • notions of lottery and expected utility
  • Decision Networks
    • modeling issues,
    • inference techniques
    • Limited Memory Influence Diagrams (LIMID)

Slides: Portinale.zip

Exam:

Kleene algebra with tests and applications to network programming

Prof. Alexandra Silva, University College London

Abstract: We will introduce Kleene algebra with tests, a language based on regular expressions that can be used to reason about simple imperative programs. We will then present NetKAT, a language for programming networks based on Kleene Algebra with Tests, and discuss several examples of network properties that can be specified and proved with NetKAT. We will review operational, denotational, and axiomatic semantics in the context of NetKAT and present an equivalence procedure based on coalgebraic techniques. Time permitting, we will also discuss a probabilistic extension of the language and its semantics.

Slides:

Exam:

Programmes


Approximation Algorithms (AA)
Probabilistic Graphical Models in Intelligent Systems (PI)
Kleene algebra with tests and applications to network programming (KN)

2017
5/03
6/03
7/03
8/03
9/03
10/03
Sun
Mon
Tue
Wed
Thu
Fri
08.00-09.00
breakfast
09.00-10.00 AA AA KN AA PI
10.00-11.00 AA AA KN AA PI
11.00-11.30 coffee break
11.30-12.30 KN KN KN AA PI
12.30-13.30 KN KN KN AA PI
13.30-15.00 lunch
15.00-16.00 AA PI PI PI -
16.00-17.00 AA PI PI PI -
17.00-17.30 tea break
17.30-18.30 arrival KN KN AA PI -
18.30-19.30 KN KN AA PI departure

ORGANIZATION

Scientific Organizing Committee


Nicolò Cesa Bianchi, University of Milano
Pierpaolo Degano, University of Pisa
Maurizio Gabbrielli, University of Bologna

Local Organization


Andrea Bandini, CeUB
Monica Michelacci, CeUB
Michela Schiavi, CeUB
Tong Liu, University of Bologna, Italy

Registration

The registration fee for the School is 550.00 Euro and includes all local expenses from the evening of 5 March to 10 March afternoon including all meals and on-site lodging in double-occupancy rooms. A reduced registration fee of 300.00 Euro is available for local students which will not use the on-site lodging facilities (it includes local expenses for the lectures, coffee breaks and lunches). It is possible to require one additional night for the students that want to leave on Saturday the 12th. In this case the additional cost is 50 Euro. Attendance is limited to 50 students and will be allocated on a first-come-first-served basis.

In order to register all applicants must fill the form available at the following link: REGISTRATION FORM.

Venue

BISS 2017 events are held in the University Residential Center located in the small medieval hilltop town of Bertinoro. This town is in Emilia Romagna about 50km east of Bologna at an elevation of 230m above sea level. View More

Via Frangipane, 6 in Bertinoro, Italy

+39 0543 446500

segreteria@ceub.it

http://www.ceub.it

Past Editions

BISS 2016:

  • ADVANCED TOPICS IN PROGRAMMING LANGUAGES
  • MODELS AND LANGUAGES FOR SERVICE-ORIENTED AND CLOUD COMPUTING
  • ALGORITHMIC METHODS FOR MINING LARGE GRAPHS

BISS 2015:

  • Game Theory: Models, Numerical Methods, and Applications
  • Protection of sensitive information
  • Introduction to Modern Cryptography

BISS 2014:

  • Big Data Analysis of Patterns in Media Content
  • An Introduction to Probabilistic and Quantum Programming
  • Development of dynamically evolving and self-adaptive software

BISS 2013:

  • Foundations of Security: Cryptography, Protocols, Trust
  • Stochastic Process Algebras for Quantitative Analysis
  • Shape and Visual Apperance Acquisition for Photo-realistic Visualization

BISS 2012:

  • Algorithms for the web and for social networks
  • Software Verification and Interactive Theorem Proving
  • Regularization methods for high dimensional learning

BISS 2011:

  • Computational Aspects of Game Theory
  • Trust in Anonymity Networks (TAN)
  • Information Integration (II)
  • Model Checking: From Finite-state to Infinite-state Systems (MCFIS)