Distributed Algorithms (DA)

Prof. Roberto De Prisco
University 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 Pedreschi
KDD 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 Dziembowski
Sapienza 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 Scarcello
University 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.