Sign In
 
 
 
  
View: 
Sort by AttachmentsUse SHIFT+ENTER to open the menu (new window).
SyllabusFilterCalendarFilter
Title Diffusione dell'informazione in grafi statici e dinamici
Teacher Prof. Pierluigi Crescenzi
Syllabus

Rumor spreading is a well-known gossip-based distributed algorithm for disseminating information in large networks. According to the synchronous push version of this algorithm, an arbitrary source node is initially informed, and, at each time step (a.k.a., round), an informed node u chooses one of its neighbors v uniformly at random, and this node becomes informed at the next time step. In the symmetric pull version of the algorithm, at each time step, a not informed node u randomly chooses one of its neighbors v; if v is informed, then u becomes informed at the next time step. Finally, the push-and-pull version is a combination of the two previous versions, in which, at each time step, each informed node executes a "push operation", and each not informed node executes a "pull operation". Rumor spreading was first introduced in the context of replicated databases, as a solution to the problem of distributing updates and driving replicas towards consistency. Successively, it has been proposed in several other application areas, such as failure detection in distributed systems, peer-sampling, adaptive machine discovery, and distributed averaging in sensor networks. Apart from its applications, rumor spreading has also been deeply analyzed from a theoretical and mathematical point of view. In particular, the completion time of rumor spreading, that is, the number of steps required in order to have all nodes informed, has been investigated in the case of several different network topologies, such as complete graphs, hypercubes, random graphs, and preferential attachment graphs. Besides obtaining bounds on the completion time of  rumor spreading, most of these works also derive deep connections between the completion time itself and some classic measures of graph spectral theory, such as, for example, the conductance of a graph. The techniques and the arguments adopted in these studies strongly rely on the fact that the underlying graph is "static" and does not change over time. It is then natural to ask ourselves what is the speed of rumor spreading in the case of "dynamic" networks, where nodes and edges can appear and disappear over time (several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peer-to-peer networks are indeed inherently dynamic). In this dynamic environment, even in the case of the simplest communication protocol that implements the broadcast operation, that is, the flooding protocol (according to which a source node is initially informed, and, whenever  an uninformed node has an informed neighbor, it becomes informed itself at the next time step), it has been shown that evolving graphs can exhibit communication properties which are much stronger than static networks. In this course, we will first review several results concerning the completion time of rumor spreading in the case of static networks. We will then present some results concerning the completion time of the flooding protocol, which have been obtained in the case of some interesting graph evolution models. Finally, we will present very recent results concerning the completion time of the push version of rumor spreading in the case of dynamic graphs.

Materials
Period
Calendar
Tutte le lezioni si terranno in Sala Seminari Ovest

PRIMA PARTE
Lunedi' 8 Luglio: 9-12
Lunedi' 8 Luglio: 15-17
Martedi' 9 Luglio: 9-12
Martedi' 9 Luglio: 15-17

SECONDA PARTE
Lunedi' 15 Luglio: 9-12
Lunedi' 15 Luglio: 15-17
Martedi' 16 Luglio: 9-12
Martedi' 16 Luglio: 15-17
 
Title Iterative rounding
Teacher Prof. Fabrizio Grandoni
Syllabus

PREREQUISITES:
Attendees are expected to be familiar with elementary notions of linear algebra, probability theory and, possibly, complexity theory and linear programming. However, all the needed definitions and lemmas will be recalled during the seminars.

ABSTRACT:
IIterative Rounding is a recent, and very powerful tool to design
approximation algorithms. The basic idea is as follows. One solves a
(carefully chosen) linear programming relaxation of the considered
NP-hard  problem. Then one rounds some variable in the fractional
solution (which corresponds to fixing part of the solution under
construction) according to proper rounding rules. The problem is then
simplified, and the process is iterated on the residual problem until
a solution to the original problem is obtained. Alternatively or in
combination to rounding, one can also relax (i.e. drop) one
constraint. This leads to "slightly" infeasible solutions. In these
seminars we will describe a representative sample of the most relevant
results obtained via iterative rounding in the literature.

The seminars will be tentatively organized as follows. In the first
week, we will introduce approximation algorithms, and present a few
foundamental results and techniques in the area. The second week will
be devoted to approximation algorithms based on linear programming. We
will first introduce linear programming, and then present some
LP-based techniques in approximation algorithms. The final part of the
week will be devoted to iterative rounding.

 

Sala Seminari W

April 8-12  and  May 6-10
Mon: 16 - 18
Tue, Wed, Thu, Fri: 9 - 11

Materials
Period
Calendar
 

Title Security at work
Teacher Prof. Luca Viganò
Syllabus

In the Internet of Services (IoS), systems and applications are no longer the result of programming components in the traditional meaning but are built by composing services that are distributed over the network and reconfigured and consumed dynamically in a demand-driven, flexible way. However, composing services leads to new, subtle and dangerous, vulnerabilities due to interference between component services and policies, the shared communication layer, and application functionality.
I will present the AVANTSSAR Platform and the SPaCIoS Tool, two integrated toolsets for the formal specification and automated validation of trust and security of applications in the IoS at design time and run time, respectively. Both toolsets have been applied as a proof of concept on a set of security problem cases drawn from industrial and open-source IoS application scenarios, thereby paving the way to transferring project results successfully to industrial practice and to standardization bodies and open-source communities.
I will present also a number of particular results that have been obtained in the AVANTSSAR and SPaCIoS projects, such as previously unknown attacks, compositionality results, novel attacker models and techniques for efficient security verification and testing.

 

 

May 27 -- June 5
Sala Seminari Ovest 11-13
(additional 4h t.b.a.)

Materials
Period
Calendar
 
 
Title Elaborazione del Linguaggio Naturale
Teacher Prof. Giuseppe Attardi
Syllabus
 
Materials
Period
Calendar
Corso della Laurea Magistrale, fare riferimento al sito Web della Didattica.

Title Apprendimento Automatico: Reti Neurali e Metodi Avanzati
Teacher Prof. Alessio Micheli
Syllabus
Materials
Period
Calendar
Corso della Laurea Magistrale, fare riferimento al sito Web della Didattica.
 
Title Analisi delle reti sociali
Teacher Prof. Dino Pedreschi
Syllabus
Materials
Period
Calendar
Corso della Laurea Magistrale, fare riferimento al sito Web della Didattica.

Title Semantica e teoria dei tipi
Teacher Prof. Ugo Montanari
Syllabus
Materials
Period
Calendar
Corso della Laurea Magistrale, fare riferimento al sito Web della Didattica.
 
Title Open Source Libraries and Tools for Computer Graphics
Teacher VCL Group ISTI
Syllabus

General purpose computation:
Eigen  (<http://eigen.tuxfamily.org/>http://eigen.tuxfamily.org/ ;- speaker Gael Guennebaud )
ViennaCL (<http://viennacl.sourceforge.net/>http://viennacl.sourceforge.net/ ;- speaker Florian Rudolf)
OpenSlam-  g2o (<http://openslam.org/g2o.html>http://openslam.org/g2o.html ;- speaker Giorgio Grisetti)

3D Geometry
VCGLib  ( <http://vcg.sf.net/>http://vcg.sf.net/ ;- speaker Fabio Ganovelli o Paolo Cignoni)
PCL (<http://pointclouds.org/>http://pointclouds.org/ ;- speaker lexandru Ichim o Federico Tombari)

3D graphics for the web
Spidergl (<http://www.spidergl.org/>http://www.spidergl.org/  ;- speaker Marco Di Benedetto)

Materials http://www.eg-italy.org
Period
Calendar
3, 4, 5 Giugno
 
Area della Ricerca CNR di Pisa

Title Reti mobili: reti ad hoc e di sensori
Teacher Stefano Chessa
Syllabus

The course aims at providing knowledge on mobile ad hoc, mesh, and sensor
networks, by describing their organizations models and architectures, and by
presenting the main design and implementation issues. The course presents
the main issues at the MAC, network, transport, and application layers. In
particular it gives emphasis to the issues in routing, energy management,
topology control, and data management. It also presents some specific
applications for wireless sensor networks, such as localization and
tracking, and the problem of integration of wireless sensor networks in
context aware systems or in other networks. Finally the course presents some
standards, such as 802.11X, 802.15.x, Bluetooth and Zigbee, and gives some
examples of commercial platforms for wireless sensor networks.

Materials
Period
Calendar

Corso della Laurea Magistrale, fare riferimento al sito Web della Didattica.

 
Title Processes inspired by the functioning of living cells: Natural Computing approach
Teacher Prof. Dr. G. Rozenberg
Syllabus

Natural Computing is an interdisciplinary research field that investigates human-designed computing inspired by nature as well as computation taking place in nature, i.e., it investigates models, computational techniques, and computational technologies inspired by nature as well as it investigates phenomena/processes taking place in nature in terms of information processing.

One of research areas from the second strand of research is  a computational understanding of the functioning of the living cell. We view this functioning in terms of formal processes resulting from interactions between (a huge number of) individual reactions. These interactions are driven by two mechanisms,  facilitation and inhibition: reactions may (through their products) facilitate or inhibit each other.

We present a formal framework for the investigation of these interactions.  We motivate this framework by explicitly stating a number of assumptions that hold for  processes resulting from these interactions, and we point out that these assumptions are very different from the ones underlying traditional models of computation. We discuss some basic properties of these processes, and demonstrate how
to capture and analyse, in our formal framework, some notions related to cell biology and biochemistry.

Research topics in this framework are motivated by biological considerations as well as by the need to understand the underlying computations. The models we discuss turned out to be novel and attractive from the theory of computation point of view. This is extensively discussed throughout the course.
 
The course is of a tutorial style and self-contained. In particular, no prior knowledge of biochemistry or cell biology is required.
 
The course is suited for master and PhD students as well as researchers and faculty members. It is of interest to computer scientists and mathematicians interested in formal models of computation as well as to bioinformaticians, biochemists, and biologists interested in foundational/formal understanding of biological processes.
 
The presented  framework was developed jointly with A.Ehrenfeucht from University of Colorado at Boulder.
 

May 20, 21, 22, 23  -- 10-13

Aula Magari, Pian dei Mantellini, 44, Siena.

Materials
Period
Calendar