Great Ideas in ICT (2014)

Once every few years the information and communication technology community is shaken by some results that fundamentally impact several core topics. These results often have strong consequence on real systems, and thus, finally, impact our everyday life as well. This course has the goal of introducing the attendees to several breakthroughs, representative of different areas, showing the practical impact they had on ICT as it is today. Lectures will be delivered by professors and researchers from the department of computer science (DI), the department of computer, control, and management engineering Antonio Ruberti (DIAG) and the department of Information, communication and electronic engineering (DIET).

Index:
    Notes
    Schedule
    Lectures
    Rules for the Ph.D. in Engineering in Computer Science
    Rules for the Ph.D. in Automatica and Operations Research
    Rules for the Ph.D. in Computer Science

Notes:

  • The lectures of July 1st and 2nd have been moved to room A6.

Schedule:

Lectures:

Computational Intractability
Lecturer: Nicola Galesi
Schedule: 3/6/2014, 9:30 - Viale Regina Elena 295, room G50
Abstract: In Complexity Theory P is the class of decision problems which are decidable efficiently, i.e. in polynomial time. NC is the class of decision problem which are efficiently solvable on a parallel machine, i.e using polylogarithmic time on a polynomial number of parallel processors. NC can be defined (modulo uniformity) as the union of NCk, where NCk is the class of boolean functions computed by boolean circuits with depth O(logk) and size polynomial. The computational strength of NCk can be powered up if we allow unbounded fan-in gates instead that fan-in 2 gates. We then speak of the ACk hierarchy. Clearly NCkACkP.
In the lecture we present the strongest separation from NP known at present, i.e. AC0NP. The formula means that there is a boolean function which is computable in NP but not computable by any polynomial size constant depth boolean circuit with unbounded fan-in gates. The original result is due to Johan Håstad. We present a proof due to Roman Smolensky and simplified by Alexander Razborov.
Notes

Multidimensional data
Lecturer: Francesco M. Malvestuto
Schedule: 5/6/2014, 9:30 - Viale Regina Elena 295, room G50
Abstract: Pooling of data is a common practice in many knowledge fields and consists in putting together data from multiple data sources in order to infer exact or approximate information of interest. In this framework, we introduce: (i) a merge operator to combine two or more multidimensional data sets, and (ii) merge expressions as combination schemes for a pool of such data sets. The merge operator is akin to the relational join operator and to the probability-theoretic fitting operator, as well as merge expressions are akin to relational join expressions. We also introduce an equivalence relation between merge expressions and provide a characterization of the “case” in which every two merge expressions are equivalent. Finally, we address the problem of computing answers to queries against a pool of multidimensional data sets, and provide efficient solutions for a special class of merge expressions (called perfect merge expressions).
NOTE: this talk will be delivered only in italian.
Paper

Biometric Systems
Lecturer: Maria De Marsico
Schedule: 10/6/2014, 9:30 - Viale Regina Elena 295, room G50
Abstract: Research on biometrics has noticeably increased. However, no single bodily or behavioural feature is able to satisfy acceptability, speed and reliability constraints of authentication in real applications. The present trend is therefore towards multimodal systems.
Five main aspects must be taken into account during the design of the proposed multimodal architectures:

  • the biometry set: to try to meet both effectiveness and efficiency;
  • the normalization method: each system may return results using different dimensionalities and scales; we propose a normalization function providing good results even when the maximum value to normalize is not known;
  • the integration schema: present systems follow three possible design choices, i.e. parallel, serial or hierarchic. We propose a new schema called N-Cross Testing Protocol, and we show how supporting tighter collaboration among different systems can enhance the obtained performances;
  • a reliability measure: it is returned by each subsystem response by response, and should be able to express how much the single result can be trusted; as a matter of fact, it might happen that not all subsystems are equally reliable, and that single responses deserve different confidence, and this is important while fusing the single results; however, this aspect is often neglected in literature; we propose two alternative reliability measures;
  • the fusion process: the integration of information by different biometries is possible in three different moments, i.e. during feature extraction, matching, or decision. The sooner a fusion is performed, the higher amount of the information extracted can be saved. A profitable choice seems to perform fusion in the matching module, where a “weighted” integration strategy can be exploited. As for the fusion rule, one could trivially decide to accept the identity with the highest returned score, or to rely on a linear combination of the subsystem responses, or even to apply a more complex fusion schema.

Slides

The PCP Theorem
Lecturer: Alessandro Panconesi
Schedule: 11/6/2014, 14:00 - Viale Regina Elena 295, room G50
Abstract: As is known, many optimization problems are NP-hard and therefore, presumably, computationally intractable. In this context, the following question arises naturally: given an NP-hard optimization problem, is it possible to compute "quickly" approximate solutions with provable guarantees? This is the starting point of the theory of approximation algorithms for NP-hard problems that, over the last forty years, has given rise to a large number of beautiful and interesting results. The PCP theorem is a fundamental result in this theory that was established in the early nineties (of the last century). The theorem makes it possible to show that, for very many optimization problems, approximate solutions are out of reach (unless P=NP).

Complexity Engineering
Lecturer: Stefano Nolfi
Schedule: 12/6/2014, 9:30 - Viale Salaria 113, room "Seminari" (third floor)
Abstract: Complexity Engineering encompasses a set of approaches to engineering systems which are composed of various interacting entities (agents, modules, components, etc) that interact among themselves and with the external environment. These systems are characterized by no central control, no or limited external control, emergence of patters and behaviour at the system level, self-organization, and self-adaptation. The synthesis of systems of this kind requires the use of new principles and methodologies that differ considerably from the standard approaches. In this lecture I will provide an overview of some of the most innovative research projects in this area.

Graph Transformations, their generalizations and applications
Lecturer: Paolo Bottoni and Francesco Parisi-Presicce
Schedule: 16/6/2014, 14:00 - Viale Regina Elena 295, room G50
Abstract: The algebraic approach to graph grammars and graph transformations proposed in the mid-70s is based on rules whose interaction can be systematically analyzed. The approach was extended 15 years later to include transformations of more general structures (such as formal specifications) to model system development. Another fifteen years and the model-driven approach to software development is an established research area which is slowly making its way into industry with preliminary tools to support model-to-model transformations in domain-specific languages. The requirements for applications have also given course to interesting theoretical developments. For example, metamodeling techniques have required the combination of transformation rules with constraints; requirements for functional behaviour of transformations brought to the development of techniques, mostly based on critical pair analysis, for deciding about termination and confluence; the need for tracing model-to-model transformations has been met by the development of the triple graph formalism. In all these cases suitable categorical structures have been identified to ensure the correctness of the adopted formal tools. The seminar will introduce the fundamental theoretical concepts underlying graph and high-level structure transformations and discuss some applications.

Quality of Experience Control in Future Internet
Lecturer: Francesco Delli Priscoli
Schedule: 17/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: This lecture focuses (i) on the Future Internet cognitive architecture supporting QoE, (ii) on a flexible way of computing QoE on the basis of a suitable set of (passive and/or active) monitorable parameters, and (iii) on the definition of QoE Agents which, for each application, perform control functions aiming at minimizing the difference between the computed QoE and the desired QoE level.
Slides

Safe control of physical human-robot interaction
Lecturer: Alessandro De Luca
Schedule: 18-19/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: Robotics research looks forward to the possibility of bringing closer humans and robots. Robots that can physically collaborate with humans will combine and enhance the skills of both the robot and the human. This will have multiple potential applications in industrial robotics (robot co-workers) and service robotics (personal assistants). To this end, robots have to be designed and controlled following new guidelines, including a mechanical lightweight construction, the inclusion of compliant actuation, the extension of the sensor suite, human-aware motion planning, and safe control of motion and force exchanges. After reviewing the current state-of-the-art on these aspects, I will present a control framework for safe physical Human-Robot Collaboration (pHRC), based on a stack of nested consistent behaviors of the robot:

  1. Safety - is the most important low-level feature of a robot that needs to work with humans, and includes fast detection and reaction to collisions (in particular, sensorless);
  2. Coexistence - is the robot capability of sharing the workspace without interfering with humans;
  3. Collaboration - occurs when the robot performs a complex task with direct human interaction and coordination.

Within this framework, a number of basic robot capabilities will be illustrated, including whole-body collision avoidance, model- or signal-based collision detection and reaction, distinguishing intentional contacts from undesired collisions, and simple verbal/gesture human-robot communication. Moreover, by combining the geometric information on the contact, as localized on line by a depth sensor, with the joint torques due to contact, as obtained by our residual-based method, allows estimating the exchanged Cartesian contact forces at any (single or multiple) point along the robot structure without the need of force/torque or tactile sensing. The estimated contact forces can be used for the design of admittance, impedance, or force control laws that focus on the behavior at the Cartesian contact level, rather than in the joint or end-effector level.
These concepts will be exemplified in human-robot interaction experiments performed in our Robotics Lab at DIAG, using a KUKA Lightweight IV robot and a Microsoft Kinect sensor, as well as with a conventional small-size KUKA industrial robot.

Acknowledgements:
The seminar will include contributions by Fabrizio Flacco and Emanuele Magrini, respectively a past and a current PhD student of our School. This work is being supported by the EU within the FP7 287513 project SAPHARI 2011-15 (www.saphari.eu)

Video footage:
An example of videos that will be shown is available clicking on this link.

Selected readings (pdf available at http://www.diag.uniroma1.it/~deluca/Publications.php):

  • M. Geravand, F. Flacco, A. De Luca, "Human-robot physical interaction and collaboration using an industrial robot with a closed control architecture," 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, D, pp. 4000-4007, 2013.
  • A. De Luca, F. Flacco, "Integrated control for pHRI: Collision avoidance, detection, reaction and collaboration," 4th IEEE RAS & EMBS International Conference on Biomedical Robotics and Biomechatronics, Roma, I, pp. 288-295, 2012 (BioRob 2012 Best Paper Award).
  • F. Flacco, T. Kröger, A. De Luca, O. Khatib, "A depth space approach to human-robot collision avoidance," 2012 IEEE International Conference on Robotics and Automation, St. Paul, MN, pp. 338-345, 2012.
  • F. Flacco, A. De Luca, "Multiple depth/presence sensors: Integration and optimal placement for human/robot coexistence," 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, pp. 3916-3923, 2010.
  • S. Haddadin, A. Albu-Schäffer, A. De Luca, G. Hirzinger, "Collision detection and reaction: A contribution to safe physical human-robot interaction," 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, Nice, F, pp. 3356-3363, 2008 (IROS 2008 Best Application Paper Award).
  • A. De Luca, A. Albu-Schäffer, S. Haddadin, G. Hirzinger, "Collision detection and safe reaction with the DLR-III lightweight manipulator arm," 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, PRC, pp. 1623-1630, 2006.

Slides - Videos

Homogeneous approximations and stabilization of nonlinear systems
Lecturer: Stefano Battilotti
Schedule: 20/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: The problems of designing globally stabilizing feedback control laws for nonlinear systems have been addressed by many authors following different routes. Many of these approaches exploit domination ideas and robustness of stability and/or convergence. In view of possibly clarifying and developing further these techniques we consider two design tools. The first one is the technique of homogeneous approximations at the origin and at infinity. The second tool is the design procedure of homogeneous feedback laws for chain of integrators. Combining these tools global asymptotic stabilization results are obtained for several classes of nonlinear systems.

The CAP theorem and the design of large scale distributed systems
Lecturer: Silvia Bonomi and Leonardo Querzoni
Schedule: 25/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: The success of the *-as-a-service business model recently shifted the demand for reliable architectures towards previously unseen scales. Modern cloud platforms represent the main result of years of research in the area of large scale distributed systems. Yet, the design of their internal architectures pushed researchers to find new solutions to well known problems in order to withstand the sheer scale and the demand for elasticity that characterize cloud scenarios. This lectures aims at analyzing current trends in the design of large scale distributed systems with a special focus on how their features are always the result of a fundamental tradeoff between their consistency, availability and partition tolerance characteristics.
Slides 1 - Slides 2

Wireless Sensor Networks: from theory to practice ... and back again
Lecturer: Andrea Vitaletti
Schedule: 26/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: The theory of wireless communication is usually based on Unit Disk Graphs (UDG). In this lecture we will discuss two fundamental results on the capacity of wireless networks (Gupta and Kumar) and on how the mobility can increase the capacity of wireless networks (Grossglauser and Tse) with a particular care in analyzing the limits of the assumptions made in such papers when they are considered in practical cases.

System Verification via Symbolic Model Checking
Lecturer: Fabio Patrizi
Schedule: 27/6/2014 9:30 - Via Ariosto 25, room A3
Abstract: This lecture introduces the verification of systems via symbolic model checking, with particular emphasis on the use of Binary Decision Diagrams (BDDs) as a way to efficiently manipulate transition systems. After discussing the basic notions of CTL model checking and briefly describing the corresponding algorithm, an in-depth presentation of BDDs is offered, which covers all fundamental aspects of the topic.
Slides

Face detection using a boosted cascade of simple features
Lecturer: Domenico Daniele Bloisi
Schedule: 1/7/2014 9:30 - Via Ariosto 25, room A6
Abstract: When we take a picture with our smartphone is normal to see a bounding box around the captured faces. The same when we tag a friend on Facebook. Actually, to detect a face in an image involves the use of multiple methods and algorithms. If the problem of face detection can be considered solved, it is thanks to the work of Paul Viola and Michael Jones. In this lecture we will go through the solutions used in the most famous face detection method. In particular, how to use the integral image representation for fast feature extraction, how to select the most discriminative features by using an Adaptive Boosting approach for face detection, and how to speed up the recognition process thanks to a cascade of weak classifiers for fast rejection of non-face sub-windows.
Slides

Sparse Least Squares on Manifolds
Lecturer: Giorgio Grisetti
Schedule: 2/7/2014 9:30 - Via Ariosto 25, room A6
Abstract: Several practical problems in robotics and in various domains of computer science can be boiled down to the solution of a Least Squares Problem. These include for instance Simultaneous Localization and Mapping (SLAM), and parameter calibration. In this course we will provide the users with means to address a wide range of LSP taking advantage of their structure to enhance performances. In parallel with the theoretical aspects we will provide several examples in octave/matlab. Prerequisites: We assume an adequate familiarity with basic linear algebra topics such as (vectors, bases, transforms, isometry, eigenvalue decompositions).

Data stream algorithmics
Lecturer: Irene Finocchi
Schedule: 3/7/2014, 9:30 - Viale Regina Elena 295, room G50
Abstract: A wide range of applications in computational sciences generate huge and rapidly changing streams of data that need to be continuously monitored and processed in one or few sequential passes, using a limited amount of working memory. Despite the heavy restrictions on time and space resources imposed by the streaming data access model, major progress has been achieved during the last fifteen years in the design of streaming algorithms for several fundamental data sketching and statistics problems. The lecture will discuss fundamental results in this rapidly evolving area, including the seminal probabilistic counting technique by Flajolet and Martin and the breakthrough results on frequency moments that earned Alon, Matias, and Szegedy the Goedel prize in 2005. The presented results have both theoretical interest and practical appeal.

3D Indoor positioning and navigation: theory, implementation and applications
Lecturer: Luca De Nardis
Schedule: 8/7/2014, 9:30 - Via Eudossiana 18, room "Sala di Lettura"
Abstract: Indoor navigation and way finding of people and objects is of tremendous interest nowadays, where the challenge in extending GPS to indoor environments limits service continuity and accuracy, and calls for a cross-disciplinary approach encompassing technologies, data representation, visual design and semiotics. This seminar will present the main solutions to the problem of indoor positioning, focusing to the case of 3D positioning, that poses the hardest challenges in heterogeneous indoor. Recent advances for both positioning and tracking will be presented, and a practical demonstration of an indoor positioning system based on Wi-Fi fingerprinting will be given.
Slides 1 - Slides 2

Rules for the Ph.D. in Engineering in Computer Science:

This course can be considered as a B-type course (2.5 CFUs) as long as both the following requirements are satisfied:

  • the student attends at least five lectures among the ones listed above; students must download this attendance sheet and fill it in to have their attendance recognized;
  • the student completes an assignment for one of the listed lectures. The assignment must be agreed with the corresponding lecturer.

Assignments will be discussed through seminar-like presentations on two dates (TBD). Students can opt to gather double the CFUS (i.e. 5 CFUs) by doubling their work (i.e. attending at least 10 lectures and completing two distinct assignments).

Rules for the Ph.D. in Automatica and Operations Research:

This course can be considered as a B-type course (2.5 CFUs) as long as both the following requirements are satisfied:

  • the student attends at least five lectures among the ones listed above; students must download this attendance sheet and fill it in to have their attendance recognized;
  • the student completes an assignment for one of the listed lectures. The assignment must be agreed with the corresponding lecturer.
  • any further lectures attended by the student will earn him 0,5 CFUs up to a maximum total of 4CFUs.

Rules for the Ph.D. in Computer Science:

All students are required to take 5 of the lectures listed above, and invited to choose among the lectures that are not strictly related to their own topic of research. Students must download this attendance sheet and fill it in to have their attendance recognized;