### Distributed Algorithms (DA)

Prof. Roberto De PriscoUniversity of Salerno (Italy)

**Summary:**

This course is an introductory course on distributed
algorithms for graduate students. The term "distributed
algorithms" covers a variety of algorithms which are
designed to run on several processors distributed over a
large (or small) geographical area. Distributed algorithms
arise in a wide range of applications (e.g., telephone
systems, banking systems, airline reservation systems,
nuclear power plant control systems). Distributed
algorithms can be classified according to several
attributes among which the most important ones are:
interprocess communication, synchronization and failure
model. In this course we will cover the basic timing models
(synchronous, asynchronous and partially synchronous) and
mostly concentrate on the message-passing interprocess
communication model. The failure models considered include
stopping, omission and Byzantine failures. We will use some
basic distributed problems, such as leader election and
consensus, to provide a broad coverage of the various
distributed models. We will study several algorithms for
the most common distributed problems and some impossibility
results. More information (including reading list and
slides) are available at this
site.

Prerequisites: Algorithms and data structures, basic knowledge of graph, automata and probability theory.

### Data Mining (DM)

Prof. Dino PedreschiKDD LAB, University of Pisa (Italy)

**Summary:**

Since databases became a mature technology and massive
collection and storage of data became feasible at
increasingly cheaper costs, a push emerged towards powerful
methods for discovering knowledge from those data, capable
of going beyond the limitations of traditional statistics,
machine learning and database querying. This is why data
mining emerged as an important multi-disciplinary field.
Data mining is the process of automatically discovering
useful information in large data repositories. Often,
traditional data analysis tools and techniques cannot be
used because of the volume of data, such as point-of-sale
data, Web logs, earth observation data from satellites,
genomic data, location data from telecom service providers.
Sometimes, the non-traditional nature of the data implies
that ordinary data analysis techniques are not applicable.
Today, data mining is both a technology that blends data
analysis methods with sophisticated algorithms for
processing large data sets, and an active research field
that aims at developing new data analysis methods for novel
forms of data. This course is aimed at providing a succinct
account of the foundations of data mining, together with an
overview of the most advanced topics and application areas,
as well as the current frontiers of data mining research.
First part of the course (*Data mining - foundations*)
covers: the basic concepts, the knowledge discovery
process, mining various forms of data (relational,
transactional, object-relational, spatiotemporal, text,
multimedia, web, etc), mining various forms of knowledge
(classification, clustering, and frequent patterns),
evaluation of knowledge, and key applications of data
mining. The second part of the course (*Data mining -
advanced concepts and case studies*) gives an
introductory account of: sequential data mining, mining
data streams, web mining, social network analysis, graph
and network mining, spatiotemporal data and mobility data
mining, privacy-preserving data mining, together with
presentations of real-life case studies in various domains,
including retail and market analysis, fiscal fraud
detection, transportation and mobility. More information
(including reading list and slides) are available at
this
site.

Reference textbooks:

Pang-Ning Tan, Michael Steinbach, Vipin Kumar.
*Introduction to Data Mining*. Pearson Addison-Wesley,
2006.

Fosca Giannotti and Dino Pedreschi (Eds.) *Mobility, Data
Mining and Privacy*. Springer, 2008.

### Modern Cryptography (MC)

Prof. Stefan DziembowskiSapienza University of Rome (Italy)

**Summary:**

The course we will provide an introduction to modern
cryptography. Over the last 3 decades cryptography
witnessed a transformation from an "art of constructing
ciphers" (in an ad-hoc, non-systematic manner) into a
mature science with solid foundations. In particular, it is
now clear how to define security of cryptographic
constructions, and how to base this security on
well-defined computational assumptions . Another big
achievement of modern cryptography are the applications
that go beyond the construction of protocols for secure
communication, like, e.g., protocols for secure multiparty
computations. The course will be divided into two parts. In
the first part, that should take the first 3 days, we will
introduce the basic cryptographic concepts (pseudorandom
generators, block ciphers, stream ciphers, hash functions,
one-way functions and trapdoor functions) and will explain
how to use them as building-blocks in the construction of
protocols for secure communication (symmetric and
asymmetric encryption, message authentication codes and
digital signature schemes). In the remaining two days we
will discuss more advanced cryptographic protocols:
commitment schemes, zero-knowledge protocols, coin-tossing
by telephone, oblivious transfer, private information
retrieval, general two-party and multi-party computations.
We would like to stress that this course is not intended to
provide an overview of the industrial cryptographic
methods. In other words, the main criterion in selecting
the topics is not the relevance to the practical
applications, but their intellectual attractiveness, and
the mathematical depth. More information (including reading
list and slides) are available at this
site.

Prerequisites: Basic knowledge of complexity theory, probability theory, algebra and number theory (including Euler's phi function, Euler's totient theorem and Chinese remainder theorem).

### Structural Methods in Database Theory (SM)

Prof. Francesco ScarcelloUniversity of Calabria (Italy)

**Summary:**

The main focus of this Database Theory course is on the
evaluation and optimization of Database queries. We start
by recalling some useful notions of Database Theory and
First Order Logic. It will be shown that perfect
optimization is impossible, because even some easier
related problems are undecidable. Then, we recall the
definitions of some complexity classes, both above NP and
inside P. The latter classes are interesting, because
problems therein can be solved efficiently by parallel
algorithms. Moreover, we present some results about the
complexity and the expressive power of query languages.
These results are based on nice technical gadgets, such as
the Ehrenfeucht-Fraisse games. The central part of the
course is about Conjunctive queries, equivalent in
expressive power to Select-Project-Join queries, which
constitute the most basic, most important, and best-studied
type of database queries. The problem of evaluating a
conjunctive query over a relational database is a
fundamental problem in the field of database systems. This
problem is NP-hard in general. However, it was shown that
there are large classes of queries, called islands of
tractability, that can be identified and answered
efficiently, that is, in polynomial-time with standard
machines, or even better with parallel machines. The idea
is to exploit the structural properties of query
hypergraphs, generalizing a classical result by Yannakakis
[1981] on the tractability of acyclic queries. This line of
research led to a number of techniques, usually called
structural methods, which extend the nice properties of
acyclic queries to more general classes of queries whose
associated hypergraphs have a "low degree of cyclicity".
Notable examples are the techniques based on the notions of
tree-width and hypertree-width. They find applications also
in other fields of computer science, such as constraint
satisfaction in AI, theorem proving, game theory, and so
on. This course presents an overview of the main results
about structural methods, starting from the theoretical
basis, and ending with recent practical applications to
query optimization in real DBMS. In particular, a number of
technical tools will be presented (e.g., alternating Turing
machines, parallel complexity classes, and graph games)
that can be useful to students even in very different
settings and for completely different problems, besides
providing a deep-understanding of the main subjects of the
course. More information (including reading list and
slides) are available at this
site.

Prerequisites: Classical notions of computational complexity theory and of algorithms and data structures, such as Turing machine, reducibility and algorithm analysis. Basic notions of Database Theory.