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 

 

https://sv-comp.sosy-lab.org/2019/results/results-verified/, 

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!

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:

• SEA 2018 - 17th International Symposium on Experimental Algorithms, 
• I-CiTies 2018  and
• ICE-TCS/GSSI Workshop 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. 

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

• "Coverage Centrality Maximization in Undirected Networks" by Gianlorenzo D'Angelo (Gran Sasso Science Institute), Martin Olsen (Aarhus University) and Lorenzo Severini (ISI Foundation) and
• "Distributed Community Detection via Metastability of the 2-Choices Dynamics" by Emilio Cruciani (Gran Sasso Science Institute), Emanuele Natale (MPII) and Giacomo Scornavacca (University of L'Aquila). 

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.

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!

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

http://www.icetcs.ru.is/.

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

email: s.p.luttik@tue.nl

Alexandra Silva

email: alexandra.silva@ucl.ac.uk

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.

Call for nominations for the Presburger Award 2019

Anca Muscholl asked me to advertise the call for nominations for the Presburger Award. I hope that members of the TCS community will nominate many of the young scientists (see the text below for the definition of "young") doing exciting work in TCS.  I wish Anca, Jukka and Thore good luck with their work, as I am sure they will be faced with some difficult choices.

Starting in 2010, the European Association for Theoretical Computer Science
(EATCS) established the Presburger Award. The Award is conferred annually at
the International Colloquium on Automata, Languages and Programming (ICALP) to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers.

The Award is named after Mojżesz Presburger who accomplished his path-
breaking work on decidability of the theory of addition (which today is called
Presburger arithmetic) as a student in 1929.

Nominations for the Presburger Award can be submitted by any member or
group of members of the theoretical computer science community except the nominee and his/her advisors for the master thesis and the doctoral dissertation. Nominated scientists have to be at most 35 years at the time of the deadline of nomination (i.e., for the Presburger Award of 2019 the date of birth should be in 1983 or later). The Presburger Award Committee of 2019 consists of Thore Husfield (Lund University and IT University of Copenhagen), Anca Muscholl (LaBRI) and Jukka Suomela (Aalto, chair). Nominations, consisting of a two page justification and (links to) the respective papers, as well as additional supporting letters, should be sent by e-mail to:

presburger-award@eatcs.org

The subject line of every nomination should start with Presburger Award 2019,
and the message must be received before December 31st, 2018.

The award includes an amount of 1000 Euro and an invitation to ICALP 2019
for a lecture.

PhD position in "Concurrency, logic and type systems" at the University of Groningen, The Netherlands

Jorge Pérez has asked me to share the following advertisement for a PhD position in his group at the University of Groningen. I trust that this might be of interest to some of the readers or this blog or their students working in concurrency theory, semantics of programming languages and types. The position is supported by a prestigious NWO VIDI career grant recently awarded to Jorge the project "Unifying Correctness for Communicating Software". Feel free to spread this call for PhD applications as you see fit. The deadline is in roughly two weeks.

PHD POSITION ON “CONCURRENCY, LOGIC, AND TYPE SYSTEMS“
(Posted: August 31, 2018)
University of Groningen, The Netherlands

We are searching for one four-year PhD position on the topics of concurrency, logic, type systems, and programming languages.

You will contribute to rigorously comparing different type systems for message-passing programs, such as session types.
These comparisons will use as reference a correspondence known as "propositions as sessions", which connects concurrency and logic in the style of the well-known Curry-Howard correspondence.
We will use the resulting comparisons to streamline existing type systems, and to guide the development of verification tools for message-passing programs.

Your PhD research will be embedded in the project "Unifying Correctness for Communicating Software", a VIDI career grant recently awarded to Dr. Jorge A. Perez by the NWO (Netherlands Organization for Scientific Research).
As such, you will join a dynamic, quickly growing research group; within the project, you will collaborate with research partners both in the Netherlands (e.g., at CWI Amsterdam) and abroad.

- Qualifications

You have an MSc degree (or equivalent) in Computer Science, Logic, Mathematics, or Artificial Intelligence, and experience in at least one, preferably two or more, of the following:

• Semantics of programming languages
• Program verification, type systems, and/or typed programming languages
• Concurrency theory and/or process calculi
• The Curry-Howard isomorphism ("propositions as types")
• Modal/substructural logics and (their) proof theory

Female candidates are encouraged to apply.

- Application and Additional Information

For further details on the position and the application procedure, please visit
https://www.rug.nl/about-us/work-with-us/job-opportunities/overview?details=00347-02S0006KOP

For further information and expressions of interest, contact Jorge A. Perez (j.a.perez@rug.nl).
See also http://www.jperez.nl/vidi

You may apply until 1 October 23:59h / before 2 October 2018 (Dutch local time).

Shortest-path algorithms applied to software engineering: A tale of cross fertilization within CS

These days, it looks as if many of us are supposed to undertake, or are expected to promise to carry out, interdisciplinary research. However, I have sometimes witnessed first-hand a lack of curiosity even to cross  the (often artificial) boundaries between areas of research within (theoretical) computer science and/or mathematics. This conservative attitude is reasonable at times, and at various stages of one's academic career, and is partly justified by the pressure to produce research output that most of us feel. I freely admit, though, that  I felt a bit uneasy when a colleague from "volume A TCS" told me at an ICALP conference that he was not going to attend  an invited talk delivered by a "volume B researcher" because that would be like going to a talk in the life sciences. (By the way, that invited talk was excellent and was delivered by a charismatic scientist. The colleague in question missed an intellectual treat.)

Perhaps naively, I feel that one of the reasons why we are in academia is that we are intellectually curious and that we should try to explain what we do to one another at least across the various disciplines within CS. Hence, I was very pleased to see this paper, which will appear in the prestigious IEEE Transactions on Software Engineering (behind the usually hefty paywall of the IEEE, alas). The paper stems from discussions between Mattia D'Emidio (a researcher in algorithmics) and Ludovico Iovino (a researcher in software engineering) who were sharing a basement office at the Gran Sasso Science Institute at the time. Those exchanges of ideas led eventually to the development of a framework that uses classic shortest-path algorithms in the selection of optimal chains of model transformations in model-driven SE. More specifically, those colleagues of mine show how to reduce the problem of computing chains of model transformations
that maximize the coverage to a shortest-path problem on weighted graphs. Moreover, they evaluate the practical effectiveness of the proposed approach by applying their automated methodology to a large set of experiments.

IMHO, this is a pleasing example of the kind of serendipitous collaboration that can arise when we are willing to have an open mind and look for possible applications to our techniques in other fields. Kudos to Ludovico, Mattia and their co-authors for going all the way and for publishing their article in a coveted outlet. I look forward to seeing more examples of cross fertilization within CS@GSSI.

Addendum 26/9/2018: Ludovico and Mattia kindly sent me two photos they took while the work was ongoing. (The all-important coffee machine is not pictured.)

Some recent achievements by the PhD students in CS at the GSSI

Like many others, I believe that students are amongst the best ambassadors for an academic institution, and that their achievements are a good indication of the quality of a graduate programme and of the mentoring skills of its associated faculty members. Therefore, it has given me great pleasure to witness the accolades received by some of the (former) students in the doctoral programme in computer science at the Gran Sasso Science Institute over the last few months.

Readers of this blog might recall that I wrote posts on the following two items.

• GSSI alumna Yllka Velaj, now at CWI, was a co-recipient of the 2018 Women@McKinsey Dissertation Award.
• Emilio Cruciani (GSSI, Italy) and Roberto Verdecchia (GSSI, Italy, and Vrije Universiteit Amsterdam, NL) were two of the authors of a research paper presented at  ICSE 2018, the 40th International Conference on Software Engineering. ICSE is the flagship conference in Software Engineering and is very selective its technical-research-paper track is the most prestigious one within the conference. Emilio and Roberto were first-year CS students at the time. 

However, there were several other events worth reporting on which I was too lazy to write a few lines on this blog. Here are three more examples.

• GSSI alumni Alkida Balliu and Dennis Olivetti, now postdocs at Aalto University in  Jukka Suomela's group, co-authored a paper presented at STOC 2018. The work on the paper was done while they were at the GSSI.
• Third-year GSSI student Ahmed Abdelsalam was part of the netgroup team at CNIT/uniroma2 that won the Interworking stream at the SoftFIRE Challenge, which addresses issues related to interoperability of the current platform with other infrastructures. In particular, Ahmed's work on IPv6 Segment Routing (SRv6) and his recently developed SRv6 aware version of the network intrusion and detection system Snort featured in the award-winning proposal. If you use Linux, you are probably already running Ahmed's software!
• In May 2018, Roberto Verdecchia received three awards for his research: 
• a bronze medal at the Research Student Competition of the International Conference on Mobile Software Engineering and Systems, 
• Runner-Up Best Paper Award at ICT4S for the study “Empirical Evaluation of the Energy Impact of Refactoring Code Smells” and, last but by no means least, 
• the best early career researcher award at the International Conference on Software Architectures (ICSA). 

I'm sure that this is just a small sample and that CS@GSSI students have more achievements of which I am not aware. It is a humbling experience to  see how smart many young researchers are. All one can hope for is to provide a good example for them and to play a small, positive role in their development as scientists.

Best PhD thesis award of the Italian Chapter of the EATCS

One of the prizes of the Italian Chapter of the EATCS is the Best Italian PhD Thesis in Theoretical Computer Science Award. This year, the committee (consisting of Vincenzo Auletta,  Ferdinando Cicalese and Carla Piazza) has unanimously decided to bestow the award on the following two young scientists:

• Michele Ciampi for his thesis "Round and Computational Efficiency of Two-Party Protocols" and 
• Luisa Siniscalchi for her dissertation "Delayed-Input and Non-Malleable Cryptographic Protocols".

Both the award recipients were PhD students at the University of Salerno working with Giuseppe Persiano and Ivan Visconti, which is remarkable.

Moreover, the award committee found that the following two theses deserved a honourable mention:

• Alessio Conte, “Enumeration Algorithms for Real-World Networks:  Efficiency and Beyond” and 
• Valeria Vignudelli, "Behavioral Equivalences  for Higher-Order Languages with Probability."

Congratulations to these young scientists. I wish them all a great career, whatever they decide to do in the future.

ICE-TCS Theory Day(s) 2018

The Icelandic Centre of Excellence in Theoretical Computer Science held its 14th annual Theory Day today. The programme is here.

Takeshi Tokuyama (Tohoku University, Japan) kicked off the day with a talk entitled Deformation of Determinants and Related Combinatorics. The talk was based on work that Takeshi did in 1986 (as a mathematics postdoc) and published in 1988. He referred to it as his "sleeping beauty" as there has been a peak of interest in that paper only  in the last ten years. Takeshi's "Weyl character formula" was even the subject of a PROMYS research project in the summer of 2013, which led to a paper that generalizes that formula to the Hall-Littlewood polynomials. The talk surveyed many interesting topics and connections with alternating sign matrices, computation of Boltzmann weights, and crystal bases.

The second half of the Theory Day 2018 was devoted to three short presentations by ICE-TCS researchers devoted to research highlights from the centre. Antonis Achilleos set himself the goal of presenting two and a half years worth of research on monitorability, carried out within the framework of the TheoFoMon project, in 15 minutes. Tigran Tonoyan presented joint work with former ICE-TCS postdoc Christian Konrad addressing the question of whether randomness helps in guessing the middle point of an on-line sequence. (Answer: It does.) Last, but not least, Christian Bean gave an overview of an ongoing project whose goal is to automate proofs of results in enumerative combinatorics. Christian presented many examples of published theorems, some of which from 2018, that can be established using their CombSpecSearcher algorithm and that were previously obtained using human ingenuity.
 
The Theory Day was preceded by a seminar by Tami Tamir (Efi Arazi School of Computer Science, The Interdisciplinary Center) on Thursday, 23 August 2018. In her talk, Tami gave an excellent introduction to the main research questions in  algorithmic game theory, introduced network formation games and discussed her work with Guy Avni and Orna Kupferman on automata formation games, where the goal of each player is given by a regular language rather than by simple reachability objectives. Tami focused on results presented in this paper, which were mostly of a negative nature. She concluded her informative and entertaining presentation by introducing her university, the Efi Arazi School of Computer Science and how they try to tackle the gender issues in computer science.

Overall, this was another good edition of the Theory Day at ICE-TCS. When we founded the centre on the 29th of April 2005, I had no idea that it would see so many installments of this event. I feel fortunate to have taken part in organizing them, to have worked with so many great colleagues in Iceland and to have met many very interesting and inspiring people along the way. Stay tuned for the Theory Day 2019, which will most likely be held in the spring of next year.
 

2018 Women@McKinsey Dissertation Award to GSSI alumna Yllka Velaj

GSSI alumna Yllka Velaj has been selected as co-recipient of the 2018 Women@McKinsey Dissertation Award (https://www.mckinsey.it/womenmckinsey-dissertation-award), which is given to a female researcher for a master or doctoral thesis on themes related to Advanced Data Analytics or Machine Learning. Yllka receives the award for her PhD thesis "Information spreading with network augmentation" that she completed at the GSSI under the supervision of Pierluigi Crescenzi (University of Florence) and Gianlorenzo D'Angelo (GSSI). The award comes with a job offer by McKinsey & Company, and with financial support to attend the Open Data Science Conference 2018, which will be held in London in the period 19-22 September 2018.

Citing the explanation of her work given by Yllka in the CWI press release:

"Understanding the dynamics that regulate the diffusion of information in complex networks has been one of the main goals in the field of complex network analysis. The problem, which is also known as influence spreading or information diffusion problem, is motivated by many applications in different fields: from marketing to epidemiology, going through the study of adoption of innovations and the analysis of social networks. In my PhD thesis, I designed new efficient algorithms which use a given budget to suggest new links to be added to the network in order to maximize the diffusion of information”.

Yllka is an Italian scientist of Albanian origin. She obtained her BSc in Computer Science and her MSc in Distributed Systems and Computer Networks from the University of L'Aquila. She was a PhD student in Computer Science in the joint PhD GSSI-IMT programme at the Gran Sasso Science Institute. After one year as a postdoctoral researcher at the University of Chieti-Pescara, in May 2018 she joined the Networks & Optimization group at CWI in Amsterdam as a winner of the fellowship programme promoted by ERCIM - the European Research Consortium for Informatics and Mathematics.

Yllka's research interests include combinatorial algorithms, network analysis, algorithm engineering and recently also algorithmic game theory.

Congratulations to Yllka, her supervisors and the CS group at the GSSI as a whole.

Call for expressions of interest for a Full Professor Position in Algorithms at the Gran Sasso Science Institute

This call for expressions of interest for a Full Professor Position in Algorithms at the Gran Sasso Science Institute might be relevant for you or for some of your colleagues. Please distribute it as you see fit. The announcement is also here.

Gran Sasso Science Institute  Computer Science Group

Expression of Interest for a Full Professor Position in Algorithms

The Gran Sasso Science Institute (GSSI  http://www.gssi.it) is a new, ambitious Centre for Advanced Studies and PhD School established in L'Aquila (Italy).

The Computer Science Group at the GSSI (http://cs.gssi.it/) invites expressions of interest for a permanent position in Algorithms at the level of Full Professor.

Candidates must have an excellent publication record, a clear potential to promote and lead research activities, and a specific interest in teaching skilled, internationally-recruited students at the postgraduate level.

Applications Applicants should submit their expression of interest by sending

• a motivation letter,
• a curriculum vitae,
• a list of publications and
• a brief research statement.

Applications (and questions regarding the application process) must be submitted in electronic form, preferably by Friday, 7 September 2018, to eoi-cs@gssi.it.

Disclaimer Please note that this is not a job advertisement. Based on the received expressions of interest, the Gran Sasso Science Institute will decide whether to open an official call for a full professor position in algorithms and which selection procedure to follow.

Additional information

1. Duties: Teaching postgraduate courses, leading internal seminars and tutoring PhD students. All activities are in English.
2. Salary: The salary will be determined on a personal basis, also taking into account past positions covered abroad. An indicative figure of the gross amount for the starting (minimum) salary is 72,431 € per year. Net income may vary depending on income taxes, local taxes, retirement plan, health care deduction and tax exemptions. Professors who have held a tenured position outside Italy for more than three years (at the corresponding level) might be eligible for a partial recognition of past services, depending on specific legal constraints.

PhD positions at IMT Lucca, Italy

I have been asked to distribute the appended call for applications for PhD positions at IMT Lucca, which, as readers of this (lately rather inactive) blog might recall, is one of the Italian institutions close to my heart. If you have some strong student looking for a PhD position or you would like to embark in PhD studies yourself in one of the research areas covered at IMT Lucca, do consider this excellent opportunity. Lucca is a lovely town in Tuscany and has a very high quality of life. This (by now somewhat dated) video gives a good introduction to IMT Lucca.

UPCOMING DEADLINE: August 3^rd, 2018 at 12:00 pm CEST

MORE INFORMATION: http://phd.imtlucca.it

We are pleased to inform you about the IMT School for Advanced Studies Lucca's two PhD Programs and their specialized tracks

Cognitive and Cultural Systems PhD Program

• - Analysis and Management of Cultural Heritage (AMCH)
• - Cognitive, Computational and Social Neurosciences (CCSN)

Systems Science PhD Program

• - Computer Science and Systems Engineering (CSSE)
• - Economics, Networks and Business Analytics (ENBA)

• No tuition fees, free room and access to IMT Canteen
• A grant of €15,300 gross/year

Candidates can apply if they obtain their (minimum) 4-year undergraduate degree NO LATER than October 31st, 2018

Child care at STOC 2018

Ilias Diakonikolas and David Kempe (STOC 2018 Local Arrangements Chairs) have asked me to post the following announcement, which will be of interest to potential STOC 2018 participants. Kudos to the STOC 2018 local arrangement chairs for organizing the first STOC providing subsidized, pooled childcare.

We are pleased to announce that we will provide pooled, subsidized child care at STOC 2018. The cost will be $40 per day per child for regular conference attendees, and $20 per day per child for students. For more detailed information, including how to register for STOC 2018 childcare, see

http://acm-stoc.org/stoc2018/childcare.html

Ilias Diakonikolas and David Kempe (local arrangements chairs)

ERC Advanced Grants to TCS Researchers

The ERC has announced the latest batch of ERC Advanced Grant recipients. The list of TCS and cryptography researchers who have been honoured with this prestigious accolade includes Peter Bürgisser (hat tip to Artur Czumaj), Jean-Sebastien Coron, Joan Daemen, Herbert Edelsbrunner, Javier Esparza, Joost-Pieter Katoen, Stefano Leonardi and Peter Sewell. Congratulations to all of the grant recipients!

Feel free to suggest additions to the list in the comments section.

Eight four-year PhD positions in Computer Science at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI), based in l’Aquila, Italy, has just issued a call for eight four-year PhD positions in Computer Science. The yearly amount of the scholarship is of € 16,159.91 gross. (An additional 50% on monthly basis may be awarded for research period abroad if approved by the GSSI.) In addition, the following facilities and benefits apply:

• all PhD students will have free accommodation at the GSSI guest house and, starting from the second year, another accommodation or a financial substitute of 350,00 Euros gross/month (to obtain the contribution, the students would have to present a rental agreement in L’Aquila);

• all PhD students will have free luncheon vouchers (1 per day, working days, except school closures, missions, other situations contemplated by the GSSI rules);

• all PhD students will have tuition fees waived;

• all PhD students will be covered by insurance against any accident and/or injury that may occur while carrying out their PhD activities.

For further details see the call for applications at

http://www.gssi.infn.it/phd/docs/2018/CallPhDXXXIV.pdf.

The deadline for applications is the 20th of June, 2018, at 6 pm (Italian time zone).

Ful professorship at Aalborg University

I have been asked to advertise this full professor position at Aalborg University.  For what it may worth, I strongly recommend CS@Aalborg as I working place. 

FULL PROFESSORSHIP AT AALBORG UNIVERSITY
At the Technical Faculty of IT and Design, Department of Computer Science, a permanent Full Professorship in Computer Science is open for appointment starting August 1, 2018 or soon thereafter. The position is enabled by a generous grant from the Poul Due Jensen Foundation and supports the focus areas “Internet of Things and Cyber-Physical Systems” and “Big Data and Artificial Intelligence”.

APPLICATION DEADLINE
Mon Apr 02 00:00:00 CEST 2018

JOB DESCRIPTION
The objective of the position is to strengthen the department’s activities on combining theory and applications in the area of distributed, embedded, and intelligent systems.  Here, current research and teaching span topics such as semantic theories; algorithms and tools for verification and validation; model-driven development, analysis and optimization; and probabilistic models and algorithms for decision making and machine learning.

The position includes funding to recruit an assistant researcher within the research field of the professorship. The assistant researcher position is for four man-years and is funded by the Poul Due Jensen Foundation.

The formal announcement including information about qualification requirements may be found at http://www.stillinger.aau.dk/vis-stilling/?vacancy=953383

You may obtain further professional information from Professor Kim Guldstrand Larsen, phone +45 2217 1159, email: kgl@cs.aau.dk. 

Cs at aalborg university
The Department of Computer Science at Aalborg University is ranked #1 in Denmark according to the Leiden Ranking.

The research at the department features a broad range of synergistic activities within research and education in the general area of computer science, including curiosity-driven research and targeted research in collaboration with industrial partners, as well as traditional university education, with a unique problem- and project-based focus, and continued education and knowledge dissemination. For more information see www.cs.aau.dk.

Noam Nisan receives the EATCS Award 2018

I just saw that the EATCS Awards Committee consisting of Artur Czumaj, Christos Papadimitriou and Jean-Eric Pin (chair) has selected  Noam Nisan as the recipient of the EATCS Award 2018 "for his decisive influence on a range of areas in computational complexity theory and for algorithmic mechanism design, an elegant and rigorous computational theory that aptly informs economics."

The laudatio for the award, which will be presented to Noam at ICALP 2018 in Prague, is available here. Congratulations to Noam!

Most Influential POPL Paper Award 2018: "Multiparty asynchronous session types" by Kohei Honda, Nobuko Yoshida and Marco Carbone

I heard the great news that the paper Multiparty asynchronous session types by the late Kohei Honda, Nobuko Yoshida and Marco Carbone has received the Most Influential POPL Paper Award 2018. See

http://www.sigplan.org/Awards/POPL/.

This award is given annually to the author(s) of a paper presented at the Symposium on Principles of Programming Languages (POPL) held 10 years prior to the award year. The papers are judged by their influence over the past decade.

The citation for the award is available from the above-mentioned web page, but I repeat it here for ease of reference:

Session types are a type-based framework for codifying communication structures and verifying protocols in concurrent, message-passing programs. Previously, session types could only model binary (two-party) protocols. This paper generalizes the theory to the multiparty case with asynchronous communications, preventing deadlock and communication errors in more sophisticated communication protocols involving any number (two or more) of participants. The central idea was to introduce global types, which describe multiparty conversations from a global perspective and provide a means to check protocol compliance. This work has inspired numerous authors to build on its pioneering foundations in the session types community and has initiated many applications of multiparty session types in programming languages and tools. It has also influenced other areas of research, such as software contracts, runtime verification and hardware specifications.

Congratulations to the authors of the paper and to the concurrency community at large, whose work over the last ten years contributed to this award and, most importantly, to significant scientific advances that are now embodied in programming languages and tools that are already having practical impact (see the work with Cognizant, Red Hat, and VMWare on Scribble, and with the OOI), and that I believe will find increasing application in years to come. 

Five Postdoctoral positions in Computer Science at Gran Sasso Science Institute

Five Postdoctoral positions in Computer Science at
Gran Sasso Science Institute in L'Aquila (Italy)
http://www.gssi.it/
Deadline:  2 March 2018 at 6 p.m. (Italian time zone)

The Gran Sasso Science Institute (GSSI, http://www.gssi.it/), a recently established international PhD school and a centre for advanced studies in computer science, mathematics, physics and social sciences offers 18 postdoctoral research positions, five of which are dedicated to computer science and more specifically to themes that are strongly connected to the pillars of the PhD program in computer science:

- Algorithmic foundations of social and computer networks.
- Software systems and services.
- Specifications and analysis of concurrent reactive systems

The research grants are awarded for two years and their yearly amount is € 36.000,00 gross.

Candidates who are preparing their doctoral thesis are eligible to apply; however, they must have obtained their PhD degree before taking up their appointment with GSSI. Selected candidates are expected to start their appointments no later than 1 November 2018.

The application must be submitted through the online form available at www.gssi.it/postdoc/ by 2 March 2018 at 6 p.m. (Italian time zone).

Each application should include the following material:

- the CV of the applicant,

- a research statement,

- up to 3 publications and

- the name and email of two references.

For more information, please consult the Call for Applications at www.gssi.it/postdoc/ or write an email to info@gssi.it.

Prospective candidates are also welcome to contact Luca Aceto (luca.aceto AT gssi.it) or Michele Flammini (michele.flammini AT gssi.it). 

PhD positions at the School of Computer Science, Reykjavik University

The School of Computer Science at Reykjavik University is advertising PhD scholarships. See https://en.ru.is/scs/ph.d-studies/ for details.

The Icelandic Centre of Excellence in Theoretical Computer Science is one of the research centres within the school and is seeking PhD candidates in the following fields: logic and concurrency (contacts: Anna Ingolfsdottir and Luca Aceto), algorithms and distributed computing (contacts: Eyjólfur Ingi Ásgeirsson and Magnús Már Halldórsson), combinatorics and automated proofs (contact: Henning Ulfarsson), types and programming-language semantics (contact: Tarmo Uustalu).

Call for nominations for the 2018 Alonzo Church Award

Catuscia Palamidessi asked me to post the call for nominations for this year's Alonzo Church Award for Outstanding Contributions to Logic and Computation. I encourage all members of the community to nominate their favourite paper or small group of papers in logic and computation published within the past 25 years.


The 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation
Call for Nominations
Introduction
An annual award, called the Alonzo Church Award for Outstanding Contributions to Logic and Computation, was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS). The award is for an outstanding contribution represented by a paper or by a small group of papers published within the past 25 years. This time span allows the lasting impact and depth of the contribution to have been established. The award can be given to an individual, or to a group of individuals who have collaborated on the research. For the rules governing this award, see: http://siglog.org/awards/alonzo-church-award/.
The 2017 Alonzo Church Award was given jointly to Samson Abramsky, Radha Jagadeesan, Pasquale Malacaria, Martin Hyland, Luke Ong, and Hanno Nickau for providing a fully-abstract semantics for higher-order computation through the introduction of game models, see: http://siglog.org/winners-of-the-2017-alonzo-church-award/.
Eligibility and Nominations
The contribution must have appeared in a paper or papers published within the past 25 years. Thus, for the 2018 award, the cut-off date is January 1, 1993. When a paper has appeared in a conference and then in a journal, the date of the journal publication will determine the cut-off date. In addition, the contribution must not yet have received recognition via a major award, such as the Turing Award, the Kanellakis Award, or the Gödel Prize. (The nominee(s) may have received such awards for other contributions.) While the contribution can consist of conference or journal papers, journal papers will be given a preference.
Nominations for the 2018 award are now being solicited. The nominating letter must summarise the contribution and make the case that it is fundamental and outstanding. The nominating letter can have multiple co-signers. Self-nominations are excluded. Nominations must include: a proposed citation (up to 25 words); a succinct (100-250 words) description of the contribution; and a detailed statement (not exceeding four pages) to justify the nomination. Nominations may also be accompanied by supporting letters and other evidence of worthiness.
Nominations should be submitted to catuscia@lix.polytechnique.fr by March 1, 2018. 
Presentation of the Award
The 2018 award will be presented at ICALP 2018, the International Colloquium on Automata, Languages and Programming. The award will be accompanied by an invited lecture by the award winner, or by one of the award winners. The awardee(s) will receive a certificate and a cash prize of USD 2,000. If there are multiple awardees, this amount will be shared.
Award Committee
The 2018 Alonzo Church Award Committee consists of the following five members: Thomas Eiter, Javier Esparza, Catuscia Palamidessi (chair), Gordon Plotkin, and Natarajan Shankar.