The PhD program organized various schools in collaboration with other PhD programs and international experts. We offered twice the "Great Ideas in Computer Science" school where experts discussed fundamental issues in our community. A series of "Advanced Topics Seminars" where international experts came to teach short courses on emerging themes of common interest were delivered. Overall, these programs helped in rounding the students preparation outsides of their thesis topic. During the years, numerous academic initiatives have been proposed, such as "How To" courses and "Brown Bag" seminars, in which the PhD students explain interesting topics of their research area.
The PhD students that obtained great results in their research, such as the acceptance of papers in national and international conference, have been both economically and physically supported from the Department for their participation.
The complete delivered activities list is the following: PhD level Schools, PhD level mini-courses, Advanced Topics Seminars. The list of past seminars is visible in the specific section. In the "Interationalization" section, the lists of partner institutes and attended PhD schools by our student is shown.
PhD schools attended by our PhD students:
- VMCAI Winter School 2020, New Orleans, USA
- BIU Winter School on Cryptography, Tel Aviv, Israel
- Stevens Institute Of Technology; Hoboken, Nj, Usa
- CaStleD@BICI: Computation and Statistics in Data science, Bertinoro (Forlì-Cesena), Italy
- ESSLLI (European Summer School in Logic, Language and Information), University of Latvia in Riga, Latvia
- IEEE RAS Summer School on Multi-Robot Systems 2019, ČVUT FEL, Praga
- 3rd International Summer School on Deep Learning, Warsaw, Poland
- 10th Lisbon Machine Learning School, Lisbon, Portugal
- Buca 2019 Google Summer School, Rocca Sinibalda, Italy
- 2019 IEEE ComSoc Summer School, Austin, Texas
- Eurographics Symposium on Geometry Processing (SGP), Milan, Italy
- Lipari School on Network and Computer Sciences, Lipari, Italy
- Reinforcement Learning Summer Scool, Lille, France
- The 9th BIU Winter School on Cryptography, Ramat Gan, Israel
- 15th Advanced School on Parallel Computing, Casalecchio Di Reno, Cineca
- VMCAI Winter School 2019, Lisbon, Portugal
Courses
Some courses are also proposed to our students. Those are focused on hot-topics in computer science.
Advanced CyberSecurity and Crypthography (16h)
Speaker: MANCINI LUIGI VINCENZO
4-7/2/2019
Aula Seminari
9:00-13:00
Automatic synthesis of reactive programs from formal specifications (9h)
Speaker: TRONCI ENRICO
15-17/5/2019
Aula Seminari
10:00-13:00
Optimization and efficiency in Graph Problems (10h)
Speaker: PETRESCHI ROSSELLA
27-31/5/2019
Aula Seminari
10:00-12:00
Word Sense Disambiguation (8h)
Speaker: ROBERTO NAVIGLI
14-15/10/2019
Aula Seminari
14:00-18:00
High level skills learningh paths
Our PhD course proposed some learning paths for specializing the students in hot topics of computer science exploiting the experience of important national and international experts in those fields.
CYBERSECURITY
- THE PROTECTION OF SPACE MISSIONS: THREATS THAT ARE SPECIFIC TO CYBER SECURITY
Space-based systems play an important role in our daily life and business. The trend is likely to rely on the use of space based systems in a growing number of services or applications that can be either safety-of-life critical or business and mission-critical. The security measures implemented in space-based systems may turn out to be insufficient to guarantee the information assurance properties, in particular confidentiality (if required by the data policy), availability and integrity of these services/applications. The various and possible cyber-attacks on space segments, ground stations and its control segments are meanwhile well known and experienced in many cases. We address the Cybersecurity specific aspects of space missions, the specific threats to space mission from cyberspace, and analyze the set of all the possible countermeasures.
18/03/2019
Location:
Aula II, ground floor of the building “ex-Facoltà di Scienze Statistiche”, in the “Main Campus”/“Città Universitaria” Sapienza, Piazzale Aldo Moro, 5, 00185 Rome
Time:
16:15-18:30
Speaker: Stefano Zatti
- AFFORDABLE SECURITY OR BIG GUY VS SMALL GUY. DOES THE DEPTH OF YOUR POCKETS IMPACT YOUR PROTOCOLS?
When we design a security protocol we assume that the humans (or organizations) playing Alice and Bob do not make a difference. In particular, their financial capacity seems to be irrelevant. In the latest trend to guarantee that secure multi-party computation protocols are fair and not vulnerable to malicious aborts, a slate of protocols has been proposed based on penalty mechanisms. We look at two well-known penalty mechanisms, and show that the so-called see-saw mechanism (Kumaresan et al., CCS 15), is only fit for people with deep pockets, well beyond the stake in the multi-party computation itself. Depending on the scheme, fairness is not affordable by everyone which has several policy implications on protocol design. To explicitly capture the above issues, we introduce a new property called financial fairness.
24/06/2019
2.30 pm
Aula Seminari, Dipartimento di Informatica
Speaker: Daniele Friolo
- AFFORDABLE SECURITY OR BIG GUY VS SMALL GUY. DOES THE DEPTH OF YOUR POCKETS IMPACT YOUR PROTOCOLS?
Uses of machine learning in security typically focus on building classifiers to determine if certain objects (behaviors, programs, network flows, etc.) are malicious, i.e., representative of an attack. Despite early successes, the rise of adversarial machine learning has called into question the robustness of many such approaches. In adversarial machine learning, an attacker learns how to generate a malicious object in such a way that it gets classified as benign by a target classifier. My talk will discuss adversarial machine learning in the domain of JavaScript exploits. I will review existing classifiers for the detection of JavaScript exploits, and outline techniques to obfuscate exploits automatically so that they no longer get identified. Our work shows that, in order to achieve JavaScript exploit detectors that are robust to adversarial samples, much still needs to be done.
09/07/2019
Time: 14:00
Venue: Aula Alfa, Ground Floor, Dipartimento di Informatica, Via Salaria 113, 00198
Speaker: Lorenzo De Carli
- MODEL-BASED AUTONOMIC SECURITY MANAGEMENT FOR DISTRIBUTED SYSTEMS
The continuous increase in the quantity and sophistication of cyber-attacks is making it more difficult and error-prone for the system administrators to handle the alerts generated by Intrusion Detection Systems (IDSs). To deal with this problem, several Intrusion Response Systems (IRSs) have been proposed lately. IRSs extend the IDSs by providing an automatic response to the detected attack. Such a response is usually selected either with a static attack-response mapping or by quantitatively evaluating all the available responses, given a set of pre-defined criteria. In this presentation, we introduce a probabilistic model-based IRS built on the Markov Decision Process (MDP) framework. In contrast with most existing approaches to intrusion response, the proposed IRS effectively captures the dynamics of both the defended system and the attacker and is able to compose atomic response actions to plan optimal multi-objective long-term response policies to protect the system. We evaluate the effectiveness of the proposed IRS by showing that long-term response planning always outperforms short-term planning, and we conduct a thorough performance assessment to show that the proposed IRS can be adopted to protect large distributed systems at run-time.
10/07/2019
2:00 pm in Aula Seminari (45min seminar)
Speaker: Stefano Iannucci
- IMPROVING SOCIAL BOT DETECTION WITH AN AML APPROACH
Social bots are automated accounts often involved in unethical or illegal activities. Academia has shown how these accounts evolve over time, becoming increasingly smart at hiding their true nature by disguising themselves as genuine accounts. If they evade, bots hunters adapt their solutions to find them: the cat and mouse game. Inspired by adversarial machine learning and computer security, in this talk we'll see an adversarial and proactive approach to social bot detection. A practical example of the application of this approach will be presented introducing the Digital DNA framework, proposed to study groups' behaviors in social networks and for bot detection.
21/11/2019
Time: 10:00
Venue: Dipartimento di Informatica, Via Salaria 113, Third Floor, Seminari Lecture Room
Speaker: Angelo Spognardi
GRAPH THEORY
- HARNESSING THE POWER OF (KNOWLEDGE) GRAPHS
The Web, traditionally viewed as a vast repository of documents, is being transformed into a huge database by the massive presence of structured data. New research challenges arise in this information space due to the intrinsic decentralized data creation and management, the lack of superimposed schema, and the availability of huge volumes of data covering diverse domains. In this talk, I will give an overview of my research activities in the areas of graph querying and explanation languages, knowledge discovery from graphs, and social networks. I will also outline some ongoing research activities centered around the marriage between machine learning and knowledge representation and reasoning.
09/01/2019
Time: 14:30
Duration: about 20 minutes
Venue: Dipartimento di Informatica, Via Salaria 113, Third Floor, Seminari Lecture Room
Speaker: Giuseppe Pirrò
- DYNAMIC GRAPH ALGORITHMS AND COMPLEXITY (A SURVEY)
In this talk I will attempt to answer the following questions I have been asked quite often: What are the current challenges in dynamic graph algorithms? What are good starting points for people who want to try working in this field? The talk will focus on challenges for basic graph problems (e.g. connectivity, shortest paths, maximum matching), and will survey some existing upper and lower bound results and techniques.
08/03/2019
11am, room G50, 3rd floor, building G (viale Regina Elena 295/B).
Speaker: Danupon Nanongkai
THEORY, ALGORYTHMS and OPTIMIZATION
- ROUND COMPRESSION FOR PARALLEL MATCHING ALGORITHMS
For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the fundamental graph problem of finding maximum matching. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. showed that if each machine has n^{1+Ω(1)} memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. In this talk, we finally show how to refute that perplexing possibility. That is, we break the above O(log n) round complexity bound even in the case of slightly sublinear memory per machine. This is a joint work with Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski, which appeared at STOC'2018.
20/02/2019
4:00pm, building F, 2nd floor.
Speaker: Artur Czumaj (University of Warwick)
- STRONG CORESETS FOR K-MEDIAN AND SUBSPACE CLUSTERING: GOODBYE DIMENSION
I will start my talk with an introduction to the area of coresets for clustering problems, give basic definitions and explain how coresets can be used to obtain distributed and streaming algorithms. During my talk, I will mostly focus on a commonly used coreset definition that has been introduced by Har-Peled and Mazumdar: A coreset is a weighted set S of points such that for all sets C of k centers we have (1-eps) cost(P,C) <= cost(S,C) <= (1+eps) cost(P,C), where cost(P,C) is the sum of distances of the points in P to their closest center in C. Then I will present a new algorithm to compute coresets that have a similar for-all guarantee as in the above definition and that consist of a number of points that is independent of the size of the input point set P and the dimension of the input space d. Joint work with David Woodruff.
10/04/2019
11am, building F, 2nd floor (viale Regina Elena 295/B).
Speaker: Christian Sohler
- STOCHASTIC INCREMENTAL ALGORITHMS FOR OPTIMAL TRANSPORT WITH SON REGULARIZER
Optimal Transport (OT) is a classic area in probability and statistics for transferring mass from one probability distribution to another. Recently OT has been very successfully used for domain adaptation in many applications in computer vision, texture analysis, tomographic reconstruction and clustering. We introduce a new regularizer OT which is tailored to better preserve the class structure. We give the first theoretical guarantees for an OT scheme that respects class structure. We give an accelerated proximal--projection scheme for this formulation with the proximal operator in closed form to give a highly scalable algorithm for computing optimal transport plans. Our experiments show that the new regularizer preserves class structure better and is more robust compared to previous regularizers.
18/04/2019
12am, room G50, building G, 3rd floor (viale Regina Elena 295/B).
Speaker: Devdatt Dubhashi
- BETTER GUARANTEES FOR K-MEANS CLUSTERING
For quite some time the best approximation algorithm for k-means were a simple local search heuristic yielding an approximation guarantee of 9, a ratio that is known to be tight with respect to such methods. In this talk, we present an improved guarantee of 6.357 via a new primal-dual approach that allows us to exploit the geometric structure of k-means. Finally, we also consider the semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we should that few queries are sufficient to recover a clustering that is arbitrarily close to the optimal one. This is based on joint works with Sara Ahmadian, Buddhima Gamlath, Ashkan Norouzi-Fard, and Justin Ward.
25/06/2019
3pm, room G50, 3rd floor, building G (viale Regina Elena 295/B)
Speaker: Ola Svensson
- ALGORITHMS, THEORETICAL COMPUTER SCIENCE AND EPIGENOMICS: MINING MATHEMATICAL LAWS FOR PREDICTING CHROMATIN ORGANIZATION AND NUCLEOSOME OCCUPANCY IN EUKARYOTIC GENOMES
Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. Starting from an open problem regarding nucleosomes and the so called 30 nm fiber, posed by R. Kornberg nearly 30 years ago, we show how the use of simple ideas from Theoretical Computer Science can surprisingly help in making progress in obtaining a mathematical characterization of nucleosome potioning in Eukaryotes, based only on knowledge of the DNA sequence. Such a characterization was conjectured not to exist. As a corollary, we obtain an algorithm for nucleosome occupancy prediction, optimal in time and guaranteeing a two orders of magnitudo improvement in time over Machine Learning counterparts. In addition, statistically sound data structures, i.e., Epigenomic Dictionaries, are also introduced in order to effectively mine epigenomic datasets for the discovery of further regularities. Again, those data structures are much more sensitive than the Machine Learning countderparts and they can profitably accomodate information from different sources. Joint Work with: Simona Ester Rombo, Dipartimento di Matematica ed Informatica, University of Palermo Italy; Filippo Utro, Computational Biology Center, IBM T.J. Watson Research, Yorktown Heights, NY, USA.
30/10/2019
3:00 pm
Place: viale Regina Elena 295/B, building F, last floor
Speaker: Raffaele Giancarlo (Dipartimento di Matematica ed Informatica, University of Palermo)
- MAX CUT IS APPROXIMATED BY SUBEXPONENTIAL-SIZE LINEAR PROGRAMS
We show that, for every epsilon>0, there is a linear programming relaxation of the Max Cut problem with at most exp(n^epsilon) variables and constraints that achieves approximation ratio at least 1/2 + delta, for some delta(epsilon)>0. Specifically, this is achieved by linear programming relaxations in the Sherali-Adams hierarchy. Previously, the only sub-exponential time algorithms known to approximate Max Cut with an approximation ratio better than 1/2 were based on semidefinite programming or spectral methods. We also provide subexponential time approximation algorithms based on linear programming for Khot's Unique Games problem, which have a qualitatively similar performance to previously known subexponential time algorithms based on spectral methods and on semidefinite programming. Joint work with Sam Hopkins and Tselil Schramm.
02/12/2019
3:30 pm
Place: viale Regina Elena 295/B, building F, last floor
Speaker: Luca Trevisan
Other activities
- Each student held lessons and laboratories in bachelor degree, master degree and workshops/seminars. Those activities improved their skills in transversal competences.
- PhD doctors could improve their skills in development and reporting on internal (Computer Science Dipartimento) and external projects. In particular, some of them have been working in industrial and corporate.
- Among the teaching activities, the PhD students also had the opportunity to follow and guide bachelor and master degree thesis students, both in the development and in the drafting of the document. This activity allowed them to obtain the title of "Correlator".