Friday, January 12, 2018

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).

Friday, January 05, 2018

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.

Tuesday, December 26, 2017

First-year computer science students at the GSSI publish paper at ICSE 2018

The paper "FAST Approaches to Scalable Similarity-based Test Case Prioritization" by Breno Miranda (UFPE, Brazil), Emilio Cruciani (GSSI, Italy), Roberto Verdecchia (GSSI, Italy, and Vrije Universiteit Amsterdam, NL) and Antonia Bertolino (ISTI - CNR, Italy) has been accepted as a technical research paper 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.

The paper contributes to the classic area of software testing, which is one of the approaches developed by computer scientists to increase their confidence that computing systems actually do what they were designed to achieve. Since the number of tests that can be performed on a computing system is enormous, test-case prioritization is a crucial element in any practical testing framework. In that approach, one prioritizes test cases so that they can detect faults more efficiently using the available limited resources.

The paper to be presented at ICSE 2018 is the first that applies techniques from data mining to test case prioritization. In particular, it shows that the use of ideas from locality-sensitive hashing, a technique stemming from research in TCS that has been employed to great effect in approximate similarity searches in audio and video data, amongst others, leads to effective test prioritization in practice, when one needs to select tests effectively amongst millions of possible ones.

Antonia Bertolino is a member of the Scientific Board for the PhD programme in Computer Science at the GSSI. Breno Miranda is currently a postdoctoral researcher in Brazil and is one of Antonia Bertolino's former PhD students. Emilio Cruciani and Roberto Verdecchia just started their second year as PhD students in computer science at the GSSI and the paper to be presented at ICSE 2018 builds on their project for the first-year Software Testing course held in early 2017 at the GSSI by Antonia Bertolino. The project itself arose from a question asked by the students during the lectures. This is what inspiring, research-based teaching can produce when there is intellectual chemistry between lecturers and students.

Congratulations to the authors (and to the computer science group at the GSSI)!

Wednesday, December 13, 2017

Tenure-track positions in CS at Reykjavik University

We are aggressively recruiting new tenure-track faculty in Computer Science to Reykjavík University (https://en.ru.is/scs/). Theoretical computer science is one of the focus areas mentioned in the call. This is a link to further information:

http://radningar.hr.is/storf/ViewJobOnWeb.aspx?jobid=3111

Whereas Reykjavík University is relatively small, I believe we can offer junior faculty attractive opportunities and an independent career path. Reykjavík is a great place for families to live, has a vibrant cultural scene and is attractive to people who enjoy the outdoors.

I would very much appreciate your help in getting this job announcement seen by interested potential candidates.

Tuesday, December 05, 2017

A letter to Franklin Foer (guest post by Frits Vaandrager)

Frits Vaandrager has sent the appended letter, which I am posting with his kind permission, to the journalist Franklin Foer. (The letter is also available here.)

Frits wrote to me saying that:
Franklin Foer published an interesting book, World without Mind, that was named a "Notable book of 2017" by the New York Times. According to Foer,  computer scientist started to use the term "algorithm" because of "status anxiety", as a form of name dropping by programmers to suggest that they were also serious scientists. In my letter to Foer I give some historic evidence that this framing is utterly incorrect, but I'd be interested in the views of colleagues from the TCS community on this matter.
Please share your views on this matter as comments to this post. It is important to put the record straight and I am glad that Frits took the time to write a cogent letter to Mr. Foer. Thank you!

Dear Mr Foer,

With much interest I have read your book “World without mind”. I agree with many of your conclusions! But as a computer scientist who has been working on algorithms for more than 30 years, I am also deeply troubled by one paragraph in your book: 

“For the first decades of computing, the term “algorithm” wasn’t much mentioned. But as computer science departments began sprouting across campuses in the 60s, the term acquired a new cachet. Its vogue was the product of status anxiety. Programmers, especially in the academy, were anxious to show that they weren’t mere technicians. They began to describe their work as algorithmic, in part because it tied them to one of the greatest of all mathematicians – the Persian polymath Muhammad ibn Musa al-Khwarizmi, or as he was known in Latin, Algoritmi. During the 12th century, translations of al-Khwarizmi introduced Arabic numerals to the west; his treatises pioneered algebra and trigonometry. By describing the algorithm as the fundamental element of programming, the computer scientists were attaching themselves to a grand history. It was a savvy piece of name-dropping: See, we’re not arriviste, we’re working with abstractions and theories, just like the mathematicians!”
 
Do you have historic sources for these strong statements? 

Much of computer science is rooted in the work of mathematicians and logicians such as Turing, Church and von Neumann. These researchers used the word “algorithm” already before computers were built, see for instance p349 of Alonzo Church’s 1936 paper “An unsolvable problem of elementary number theory”. Together with Turing’s 1936 paper “On computable numbers, with an application to the entscheidungsproblem”, this paper forms the basis for the so-called Church-Turing thesis, which in turn laid the foundation of theoretical computer science. The computer science pioneers definitely knew the term “algorithm”!!

The term “algorithm” was maybe not used so often by computer scientists during the initial years (often they used terms such as “effective procedure” or “computable function”), but that certainly changed in 1958 with the influential work on ALGOL (short for Algorithmic Language), a family of imperative computer programming languages. The researchers who worked on Algol e.g. Bauer, Backus, Dijkstra, Perlis, Naur, van Wijngaarden & McCarthy were established scientists who definitely did not suffer from “status anxiety”. Backus, Dijkstra, Perlis, Naur and McCarthy later received the Turing award, the major prize for computer science research, for their groundbreaking research.

In order to appreciate the wonderful scientific work on algorithms, I can recommend you, for instance, to read the book Algorithmics – The spirit of computing by David Harel. I hope that, after studying this book, you will be also convinced that the fact that programmers used the term algorithm is not a form of name dropping. The work on algorithms since the advent of computers very much fits into the tradition of the work started by great scientists like Euclides and al-Khwarizmi.

Scientific knowledge may always be used for both good and bad things. Like you, I am very concerned about the use of algorithms by Google, Facebook, Apple and Amazon. But I disagree with any suggestion that there is no science behind computer science algorithms!

Looking forward to your reaction, with best regards,

Frits Vaandrager
Professor of Computer Science at Radboud University
Nijmegen, December 4, 2017

Thursday, November 16, 2017

Two and a half months at the Gran Sasso Science Institute

About two and a half months have passed since I started working at the Gran Sasso Science Institute (GSSI). I still have much to learn about the functioning of the Italian university system (and even of the GSSI), and it is already clear that there will be many of its aspects that I will probably never learn. However, my impression so far is that the level of bureaucracy in Italy is definitely higher than that in the countries where I have previously worked.

On page 88 of this interesting article, the historian Rogers Hollingsworth writes:
"One of the factors influencing creativity at the level of the nation state is the institutional environment in which scientists conduct research. I code scientific institutional environments as ranging from weak to strong. Weak institutional environments exert only modest influence (1) on the appointment of scientific personnel of research organizations, (2) in determining whether a particular scientific discipline will exist in a research organization, (3) over the level of funding for research organizations, (4) in prescribing the level of training necessary for a scientific appointment (e.g., the habilitation), and (5) over scientific entrepreneurship (e.g., the norms of individualism that socialize young people to undertake high-risk research projects). Strong institutional environments are at the opposite end of the continuum on each of these characteristics. Weak institutional environments have tended to facilitate greater scientific creativity in a society than strong institutional environments..."
(The emphasis is mine.) According to the above description, the Italian scientific institutional environment can only be classified as strong, for good or for worse. Fortunately, the GSSI is a centre for advanced studies and an international PhD school. Even though it has to follow the Italian law, with all its quirks, it is more nimble and less rigid  than the average Italian university. Moreover, most of the bureaucracy is hidden to the junior members of our faculty, such as the assistant professors, who can largely concentrate on the scientific work.
 
I have always appreciated the work that Italian researchers have been carrying out over the years, but what I have seen so far has increased my esteem for them even more. In spite of the extremely rigid system within which they are forced to operate, they manage to be productive and to maintain a strong commitment to their research work, achieving a high level of scientific production, both in quality and in quantity. The GSSI hosts a number of top-class academics in its four fields of research (computer science, mathematics, physics and social sciences) and this creates a stimulating environment for faculty and students alike.

The computer science group at the GSSI is still too small, but it seems to me that it punches well above its weight. Its members are very dedicated and have done an amazing job since the beginning of the GSSI adventure. (It was a humbling learning experience for me to present their achievements to the Scientific Advisory Board of the GSSI last Monday.)

It is clear that our group needs to grow, but we want to do so well. If you work in one of the research areas that we cover, at their intersection or in sister ones, and you think you'd be interested in working in L'Aquila with our faculty, do drop one of us a line, sending your CV and an expression of interest. We are keen to recruit strong researchers at all levels who can help us build the best international research centre in computer science we can. I can vouch that the computer science group at the GSSI provides young researchers with early-career autonomy in a nurturing environment, which isn't very common in Italy (as far as I know), and with the opportunity to become involved in the supervision of doctoral students. There are also resources for inviting collaborators and organizing thematic events, amongst other things.

It will be interesting to see how the computer science group will develop at the GSSI over the coming year. 

Friday, September 29, 2017

Reykjavik University: A THE top-500 university

Reykjavik University is in the top 500 universities in the world, according to the THE rankings. See here for details about my Icelandic workplace.

This is the first time RU appears on the list, which is an excellent result for a young and specialized university.

Even though all rankings should be taken with a pinch of salt, this is a remarkable achievement for a small university in a tiny country. Congratulations to my colleagues at Reykjavik University, who made this achievement possible with their work in research, teaching and service to the academic community.