Monday, January 14, 2019

One postdoc position available at Reykjavik University


Open Problems in the Equational Logic of Processes

School of Computer Science, Reykjavik University

One Postdoc Position

Applications are invited for one post-doctoral position at the School of Computer Science, Reykjavik University.  The position is part of a three-year research project funded by the Icelandic Research Fund, under the direction of Luca Aceto (Gran Sasso Science Institute and Reykjavik Universityand Anna Ingolfsdottir (Reykjavik University) in cooperation with Bas Luttik (TU Eindhoven) and Alexandra Silva (University College London). The overarching goal of this project is to solve some of the challenging open problems in the equational axiomatization of behavioural equivalences over process calculi. Interested applicants can contact Luca Aceto (email: luca@ru.is) for further details on the research proposal.

The successful candidate will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). For information about ICE-TCS and its activities, see

Moreover, she/he will cooperate with Bas Luttik and Alexandra Silva  during the project work and will benefit from the interaction with their research groups at TU Eindhoven and University College London. The postdoc will also have a chance to interact with Clemens Grabmayer and the CS group at the Gran Sasso Science Institute (http://cs.gssi.it/), L'Aquila, Italy. 

Qualification requirements
Applicants for the postdoctoral position should have, or be about to hold, a PhD degree in Computer Science or closely related fields. Previous knowledge of at least one of concurrency theory, process calculi, (structural) operational semantics and logic in computer science is highly desirable.

Remuneration
The wage for the postdoctoral position is 
530,000 ISK (roughly 3,830  € at the present exchange rate) per month before taxes. (See http://payroll.is/en/ for information on what the wage will be after taxes.) The position is for two years, starting as soon as possible, and is renewable for another year, based on good performance and mutual satisfaction.

Application details

Interested applicants should send their CV, including a list of publications, in PDF to all the addresses below, together with a statement outlining their suitability for the project and the names of at least two referees.

Luca Aceto
email: luca@ru.is

Anna Ingolfsdottir
email: annai@ru.is

We will start reviewing applications as soon as they arrive and will continue to accept applications until the position is filled. We strongly encourage interested applicants to send their applications as soon as possible and no later than 8 February 2019.

Tuesday, January 01, 2019

Thirty-five years of "Testing Equivalences for Processes" (TCS edition)

Thirty-five years ago, Rocco De Nicola and Matthew Hennessy published the archival paper introducing the notions of testing equivalence over concurrent processes in the journal Theoretical Computer Science. These testing equivalences embody in a natural and mathematically elegant way the intuitive idea that two processes should be equated unless they behave differently when subjected to some ‘experiment’ or ‘test’. The origin of this notion of equivalence can be traced back to Gottfried Wilhelm Leibniz (1646–1716), who stated that two mathematical objects are equal if there is no test to distinguish them. In the semantics of programming languages, its earliest precursor is, to the best of my  knowledge, the notion of contextual equivalence proposed by Morris in his doctoral dissertation.

In general, given a set of processes, a set of tests and a relation between processes and tests that describes when a process passes a test, one can apply Leibniz’s motto and declare two processes to be equivalent if if they pass exactly the same set of tests. In the work of De Nicola and Hennessy, processes are states in some labelled transition system. A test is itself a process, which interacts with a concurrent system under observation by hand-shake synchronisation and uses a distinguished action to report success in its observation. Since both processes and tests may be nondeterministic, the interaction between a process and a test may lead to different outcomes depending on how the two systems resolve their nondeterministic choices in the course of a computation. This led De Nicola and Hennessy to define three notions of testing semantics, which are naturally expressed in terms of preorders over processes.

In the so-called may semantics, a process q is at least as good as some process p if the set of tests that p may pass is included in the set of tests that q may pass. In may semantics, possible failure under a test is immaterial and therefore nondeterminism is angelic. On the other hand, one may take the view that failure in the testing effort is catastrophic, in the sense that a process that may fail some test is just as bad as one that always fails it. The notion of testing semantics that captures this viewpoint is the so-called must semantics, according to which a process q is at  least as good as some process p if the set of tests that p must pass is included in the set of tests that q must pass. Finally, a third testing preorder over processes is obtained as the intersection of the may and must preorders described above. According to this more refined view of process behaviour, a process that always fails a test is worse than one that may pass that test, which in turn is worse than one that always passes it.

De Nicola and Hennessy explored the rich theory of the testing semantics in their seminal TCS paper (see this monograph for a classic, book-length treatment), where each of these semantics is given operational, denotational and axiomatic accounts that are in agreement one with the other. Their ideas and the accompanying technical results have had an enormous impact on further research, as witnessed, among other things, by the 1,640 citations to the TCS paper published in 1984 (source: Google Scholar today).

Happy 2019 to everyone.



Tuesday, December 18, 2018

Two recent achievements by CS@GSSI researchers

This week has seen two more achievements by some of my colleagues in the CS group at the GSSI. 
 
Omar Inverso, postdoctoral researcher in the Computer Science group at the GSSI, has won a Silver Medal at the 2019 8th International Competition on Software Verification (SV-COMP 2019). Quoting from the paper at https://www.sosy-lab.org/research/pub/2017-TACAS.Software_Verification_with_Validation_of_Results.pdf

"Software verification is an increasingly important research area, and the annual Competition on Software Verification (SV-COMP) is the showcase of the state of the art in the area, in particular, of the effectiveness and efficiency that is currently achieved by tool implementations of the most recent ideas, concepts, and algorithms for fully-automatic verification."

As can be seen from the results of the competition at 
 

Omar Inverso's Lazy-CSeq, a software tool for the automated analysis of complex concurrent programs, came second in the category ConcurrencySafety and was beaten only by a tool developed by a Chinese team from Tsinghua University, which is widely considered the best technical university in China. This is a remarkable achievement and continues Omar Inverso's success in that competition, where he won Gold and Silver medals in 2016, and Silver and Bronze medals in 2017, in the Concurrency category. It is also worth noting that Omar Inverso is developing Lazy-CSeq and related software-analysis tools alone, whereas competing tools are largely the result of a team effort.

Third-year Computer Science students  Emilio Cruciani and  Roberto Verdecchia have done it again! They have followed up on their ICSE 2018 paper with  Breno Miranda(UFPE, Brazil) and Antonia Bertolino (ISTI - CNR, Italy)  (see http://processalgebra.blogspot.com/2017/12/first-year-computer-science-students-at.html for a few words on that achievement) with another paper, entitled "Scalable Approaches for Test Suite Reduction ", that has been accepted to the ICSE 2019 Technical Track (https://2019.icse-conferences.org/track/icse-2019-Technical-Papers#event-overview). To put this achievement into perspective, ICSE is the premiere conference in software engineering. ICSE 2019 had 529 submissions, out of which  109 papers were accepted (with an acceptance rate of 21%).

The ICSE 2019 paper present an approach to test-suite reduction, which aims at decreasing software-regression-testing costs by selecting a representative subset from large-size test suites. It presents a family of novel, very efficient approaches for similarity-based test suite reduction that apply algorithms borrowed from the big-data domain together with smart heuristics for finding an evenly spread subset of test cases. The results of the experimental evaluation show that the approaches yield a fault detection loss comparable to state-of-the-art techniques, while providing huge gains in terms of efficiency.
 
Congratulations to Emilio, Omar and Roberto!

Wednesday, December 12, 2018

CS@GSSI: Highlights for 2018

It is the time of the year when one sees "Best of 2018 in X (for some X)"/"Year in Review" articles appear just about everywhere in print and on the internet. Since I need to deliver a ten-minute presentation to the Scientific Advisory Board of the  Gran Sasso Science Institute (GSSI) discussing the highlights in 2018 for the computer science group, I thought that it might be a good idea to prepare for that task by following the trend and dumping some of my thoughts in this post.

So what were the main achievements of the CS@GSSI group in 2018? With only ten minutes at my disposal, I needed to make some hard choices and I decided to focus on the kudos that were bestowed on our students. After all, "our students' success is our success" and the GSSI is also an international PhD school.

Before I do so, however, let me give a bird's eye view of the research activity of the group and of the changes in personnel we have had in 2018. In November 2017, the group consisted of two full professors (one, Michele Flammini,  on loan from the University of L'Aquila), one tenure-track assistant professor, two non-tenute-track assistant professors and one postdoc. Those six people had to manage about 40 PhD students at various stages in their doctoral studies and this task could only be achieved with the help of external supervisors. Today, the faculty members in the group have not changed, but  the number of postdocs has grown to eight from November 2018. (We have been very lucky in hiring some superb young scientists!) At the same time, we have admitted eight new PhD students, seven of whom are from outside Italy and three are women, and are happy to have Shantanu Das (Marseille) as a visiting professor for a few months.

Publications

Despite the work resulting from having to manage a fairly large number of PhD students, give courses and deal with the administrative red tape that accompanies just about everything at an Italian university, my colleagues at CS@GSSI and our students managed to produce a substantial number of high-quality publications including 16 journal papers, 53 conference papers, four book chapters, two edited volumes and five refereed short abstracts/posters. (Note that these are publications with GSSI affiliation, so there is only one paper authored by one of the new seven postdocs.)

Essentially every high-quality conference in the fields of research covered by CS@GSSI has seen the presentation of at least one paper from the group. To wit, my colleagues published seven papers in top AI conferences (AAAI, AAMAS, IJCAI), seven papers in high-quality TCS conferences (including STOC and ICALP), two papers in the top SE conference (ICSE) and one in the top conference on foundations of programming languages (POPL). All the journal papers are in high-class outlets. Here let me just highlight that I have covered the result of a collaborative effort between researchers in algorithms and software engineering elsewhere.

Two of the papers are co-authored with researchers from the Urban Studies group at at the GSSI, and witness the cross-disciplinary work carried out by my colleagues in topics such as Smart Cities.

Student awards and honours

It is hard to choose what student achievements to highlight, so let me say that all our PhD students had  an excellent year and that the three contributions below are just a small sample of the work done by the PhD students at the institute.
  • CS@GSSI student Ahmed Abdelsalam has contributed to the proposal that won the first prize at the Interworking stream at the SoftFIRE Challenge 2018, which carries a 40,000 € prize. Ahmed's work on IPv6 Segment Routing (SRv6) and his recently developed SRv6-aware version of the network intrusion and detection system Snort played a key role in the award-winning proposal. Every Linux user is running GSSI software! Ahmed's network intrusion and detection system might well be the work carried out at the GSSI that is most widely used worldwide and has the most impact on a day to day basis. Ahmed now works for Cisco in Rome. 
  • CS@GSSI student Emilio Cruciani has published papers in the top conference in software engineering (ICSE) (jointly with  fellow student Roberto Verdecchia, Breno Miranda and Antonia Bertolino; see here for a post I wrote on one of the two papers), and in two of the three top conferences in the theory of artificial intelligence (AAAI and AAMAS). To put these achievements in perspective, a conference like AAAI has over 7,000 submissions and an acceptance rate of around 16%.
  • CS@GSSI student Roberto Verdecchia, whom I already mentioned in the previous highlight, has received the Early Career Researcher Award from the International Conference on Software Architectures. 
Let me also mention that my colleagues also receive awards for their sterling service to the community. By way of example, Catia Trubiani received an Exceptional Reviewer Award from ICSA. 
Software tools

Despite its very limited size, CS@GSSI devotes a substantial amount of effort to tool development. I have already mentioned the contribution given by Ahmed to the Linux kernel (IPv6 SHR). Other software tools developed by my colleagues include:
  • Omar Inverso's Lazy-CSeq, an award-winning automated analysis of complex concurrent programs, and his CSeq-fpmath and CSeq-fpmath-ILP, for the automated verification of data-intensive programs such as control system software;
  • a prototype tool for the automated analysis of multi-agent-based models, developed by Luca Di Stefano, Omar and Rocco De Nicola. 
Addendum dated 16 December 2018:  Omar Inverso's Lazy-CSeq has just received yet another accolade! It has won a Silver Medal at the 2019 8th International Competition on Software Verification (SV-COMP 2019). As can be seen from the results of the competition available here, Omar's tool Lazy-CSeq came second in the category ConcurrencySafety and was beaten only by a tool developed by a Chinese team from Tsinghua University (which is widely considered the best technical university in China).
Events

The CS@GSSI group organized the following events in 2018:
All the events were well attended and fruitful. (To whet you appetite, let me say that we will be organizing SIROCCO 2019.)

Collaborations with other groups at the GSSI

I think that it is fair to say that the CS group at the GSSI is playing the role of glue within the institute: like Nokia claimed it used to do, it is connecting people! In fact, I do believe that CS is and will increasingly become the hub of the institute. Here are some examples to substantiate my claim, in addition to the two papers published jointly with researchers in Urban Studies.
  • We have run joint seminars with Urban Studies and Mathematics (and brought an ICM 2018 invited section speaker to the GSSI). 
  • We have a joint postdoc with Urban Studies (Geotouch project on tourist flow). 
  • We have submitted two joint project proposals with Urban Studies. 
  • Catia Trubiani participates in a  COST action related to machine learning with researchers in the Astroparticle Physics group. 
Submission of grant proposals

We have at least eight grant proposals under evaluation, submitted to funding agencies in Italy, European Union and Iceland. Moreover, we have received funding for one PhD position from a local start-up company and from the municipality of L'Aquila for a project on an innovative platform for tourism.

Of course, I hope that some of those grant applications will be successful. However, money isn’t an end in itself. Lots of it does not necessarily lead to good, let alone great, science! In my career, I have seen richly funded projects produce much less than expected (and sometimes no science at all), whereas some grassroots projects with little or no funding have led to great advances.

I do hope that, regardless of the funding situation, my colleagues will go from strength to strength, produce the best work they can and serve as role models for the PhD students at the GSSI. One cannot ask for more.

Self-evaluation for 2018
  • The CS group is already a productive and internationally respected group, despite its very limited size.
  • We are lucky to have excellent students, and brilliant postdocs and young faculty.
  • CS is already a hub at GSSI, but is grossly over-committed. We need to hire a good number of excellent faculty soon! If you are interested, send an expression of interest.

The future

I think that 2019 will be a key year for the growth of CS@GSSI. I looked at my crystal ball and made a few predictions, but I prefer to air them during the meeting with the Scientific Advisory Board of the GSSI on Saturday without making them public on the internet. After all, "verba volant, scripta manent!"

I just hope that the GSSI will continue to give us the freedom to hire the best people we can find and allow us to do our work. 






Wednesday, December 05, 2018

Two papers by GSSI researchers at AAAI 2019

The main track of AAAI 2019 will feature the presentation of two papers by CS@GSSI researchers. The two papers are
The paper by Gianlorenzo, Martin and Lorenzo (who is a CS@GSSI alumnus)  contributes to the study of one of the main tools in the analysis of social networks, viz. centrality metrics. Since central nodes are very influential in their network, increasing the centrality of a network user is a widely studies optimization problem in network analysis. Gianlorenzo, Martin and Lorenzo have studied the centrality maximization problem in undirected networks for one of the most important shortest-path-based centrality measures, namely the coverage centrality. They give several hardness results, approximation algorithms and an experimental study of their effectiveness.

The paper by Emilio, Emanuele and Giacomo analyzes the behaviour of a simple majority-based dynamics on a class of networks that present a clustered structure. By combining symmetry-breaking techniques and concentration of probability arguments with a linear algebraic approach, it provides the first symmetry-breaking analysis of dynamics for non-consensus problems on non-complete topologies. The analysis shows that, when the agents of the networks randomly initialize their states, the 2-Choices dynamics makes the network quickly converge to a configuration where the agents have a state that identifies the cluster to which  they belong. The 2-Choices dynamics can be seen as a simple distributed Label Propagation Algorithm (a widely used class of heuristics for graph clustering) with quasi-linear message complexity. In this setting, the paper represents the first rigorous theoretical result. Moreover, in the context of evolutionary biology, it gives a proof of principle of sympatric/parapatric speciation, in which there is no complete geographical isolation between the species: No simple dynamics was proposed before to explain such a fundamental phenomenon.

Congratulations to Emilio, Gianlorenzo and their coauthors! It is always a pleasure to see young researchers in one's group succeed and develop their careers. Emilio Cruciani is a beginning third-year student who already has an impressive track record of high-quality publications. Keep him in mind for postdoctoral and tenure-track positions, once he finishes his studies!

The AAAI conference promotes research in artificial intelligence and is one of the premier conferences in AI, where researchers, practitioners, and scientists meet to present and discuss most recent trends and results in the field of artificial intelligence. This year it received a record number of over than 7,700 submissions of which 1,150 were accepted (with an acceptance rate of 16.2%). The list of accepted papers is at https://aaai.org/…/uplo…/2018/11/AAAI-19_Accepted_Papers.pdf.

Thursday, November 29, 2018

Calls for expressions of interest in academic positions in CS at the Gran Sasso Science Institute

The CS group at the Gran Sasso Science Institute has issued a call for expressions of interest in tenured/tenure-track academic positions. One call is for an associate or full professor position in the field of machine learning. The other is for positions at all academic levels in the areas of algorithms, formal methods (broadly construed) and software engineering.

The GSSI is an international PhD school and a centre for advanced studies in physics, mathematics, computer science and social sciences. It offers a truly international research environment and we are planning to grow substantially in CS in the coming years. Do consider expressing your interest for a position with us and spread the word!

Wednesday, October 24, 2018

One PhD position at the School of Computer Science, Reykjavik University

The following call for a PhD position at Reykjavik University might be of interest to some of your students. Feel free to distribute it as you see fit.


Open Problems in the Equational Logic of Processes

School of Computer Science, Reykjavik University
One PhD Position

Applications are invited for one PhD position at the School of Computer Science, Reykjavik University.  The position is part of a research project funded by the Reykjavik University Research Fund, under the direction of Luca Aceto (Reykjavik University) and Anna Ingolfsdottir (Reykjavik University) in cooperation with Bas Luttik (TU Eindhoven) and Alexandra Silva (University College London). The overarching goal of this project is to solve some of the challenging open problems in the equational axiomatization of behavioural equivalences over process calculi. Interested applicants can contact Luca Aceto (email: luca@ru.is) for further details on the research proposal.

The successful candidate will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). For information about ICE-TCS and its activities, see

Moreover, she/he will cooperate with Bas Luttik and Alexandra Silva  during the project work and will benefit from the interaction with their research groups at TU Eindhoven and University College London. The PhD student will also have a chance to interact with Clemens Grabmayer and the CS group at the Gran Sasso Science Institute (http://cs.gssi.it/), L'Aquila, Italy.

Qualification requirements

Applicants for the PhD fellowship should have, or be about to obtain, an MSc degree in Computer Science, or closely related fields. Some background in concurrency theory and mathematical competence are desirable.

Remuneration
The PhD position provides a stipend of 420,000 ISK (roughly 3,110 € at the current exchange rate) per month before taxes, for three years, starting as early as possible.  In addition, the student will have 300,000 ISK per year available for research-related travel.

Application details

Interested applicants should send their CV, including a list of publications, in PDF to all the addresses below, together with a statement outlining their suitability for the project and the names of at least two referees.

Luca Aceto
email: luca@ru.is

Anna Ingolfsdottir
email: annai@ru.is

Bas Luttik

Alexandra Silva

We will start reviewing applications as soon as they arrive and will continue to accept applications until the position is filled. We strongly encourage interested applicants to send their applications as soon as possible and no later than 23 November 2018.