Friday, October 02, 2015

Running a research centre in TCS in Iceland for ten years

ICE-TCS, our small research centre in theoretical computer science at Reykjavik University, is ten years old. Magnús M. Halldórsson, Anna Ingólfsdóttir and I, together with some other kindred spirits, decided to found the centre in the spring of 2005 to exploit the available scientific strengths, whatever those might be, in theoretical computer science  and discrete mathematics in order to
  • focus the research efforts, and establish synergies amongst the active researchers in Iceland,
  • attract outstanding researchers in Theoretical Computer Science to Iceland for short- or long-term visits leading to collaborations with local researchers and to improvements in the Icelandic research environment,
  • organize international conferences and workshops in Theoretical Computer
    Science in Iceland to put the country firmly on the map as a recognized
    conference location for high quality events in the field, and
  • attract young, outstanding students from Iceland to this research area.
The research centre was started as a collaboration between the Department of
Computer Science, Faculty of Engineering, University of Iceland, and the School of Computer Science, Reykjavik University. However, all the activities of the centre have taken place at Reykjavik University since Magnús, who has been the director of ICE-TCS since its inception, took up a professorship at the School of Computer Science at Reykjavik University in August 2007.

The inspiration for starting the centre derived from the experience that Anna and I had with BRICS (the Basic Research in Computer Science centre of the Danish National Research Foundation), which ran, with generous funding, in Aarhus and Aalborg from 1994 till 2006. 

It is not up to me to say whether we have achieved any of the above-mentioned objectives over the last ten years. I encourage our scientific advisory board and you to have a look at the ICE-TCS web site to get an idea of the main events that we have organized over the last decade and to form your own opinions. Here I will simply limit myself to saying that I do believe that starting the centre was necessary at that time and that without ICE-TCS the academic environment in computer science in Iceland would have been much less attractive and interesting  for those amongst us who try to carry out research in TCS and discrete mathematics. The Icelandic research community in (T)CS is simply too small to consist of islands of isolated individuals. IMHO, one needs centre-like structures to sustain a community that is capable of organizing events such as a weekly seminar series that one takes for granted in larger CS departments.

A former colleague from Aalborg University used to say that "lone rangers die".  The brightest and most motivated researchers amongst us would be able to keep producing top-class work even alone on Mars, but I do believe that, for the common mortals amongst us, the existence of a research ecosystem, no matter how small, does help us stay "alive", in the sense of  Paul Erdős, a little longer.  I hope that my colleagues at ICE-TCS over the years feel that the centre has played a positive role in their careers and  in their daily work.

Despite our chronic lack of centre-specific funding, we have made the most of the lure of Iceland and have succeeded in attracting guests to ICE-TCS. To do so, we have had to use every available source of ad hoc funding, not to mention the fact that many of our guests often paid for their own travel and accommodation. (This is where being located in a hip place like Iceland does help.) On behalf of ICE-TCS, I thank all the colleagues who have graced our centre with their visits, which have often led to joint papers and long-term collaborations.

I like to think that we have done our share for the TCS by hosting the best attended ICALP ever in 2008, DisCoTec 2011, 6th International Federated Conferences on Distributed Computing Techniques, and the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012) amongst other events. If you are interested in visiting us, combining business and pleasure, you might consider submitting to the  15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) or to LICS 2017. In addition, we have organized an annual theory day since 2005, with the goal of preaching the gospel of TCS to the local CS community and to our students. We have taken part in the Alan Turing Year and we followed it up with a seminar series on Pearls of Computation, which, despite our best intentions, is not attracting as many participants as we had hoped.

In summary, these have been ten very exciting years and we do not plan to close the centre yet. Starting the centre is a decision I personally do not regret, despite the work needed to keep it ticking. Whether my colleagues and I will have the energy and the drive to keep going for a few years more is something I do not know. I just hope that some of our young and enthusiastic members will step up to the challenge of making the centre thrive in its second decade of existence. Time will tell whether ICE-TCS will become a teenager.

Thursday, October 01, 2015

Call for Nominations: EATCS FELLOWS 2016

  • VERY IMPORTANT: all nominees and nominators must be EATCS Members
  • Proposals for Fellow consideration in 2016 should be submitted by DECEMBER 31st, 2015 by email to the EATCS Secretary ( The subject line of the email should read "EATCS Fellow Nomination - surname of candidate".

The EATCS Fellows Program is established by the Association to
recognize outstanding EATCS Members for their scientific achievements
in the field of Theoretical Computer Science. The Fellow status is
conferred by the EATCS Fellows-Selection Committee upon a person
having a track record of intellectual and organizational leadership
within the EATCS community.  Fellows are expected to be “model
citizens” of the TCS community, helping to develop the standing of TCS
beyond the frontiers of the community.

In order to be considered by the EATCS Fellows-Selection Committee,
candidates must be nominated by at least four EATCS Members.  
Please verify your membership at

The EATCS Fellows-Selection Committee consists of 

- Rocco De Nicola (IMT Lucca, Italy, chair) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France)
- Dorothea Wagner (Karlsruhe, Germany)
- Roger Wattenhofer (ETH Zurich, CH)


A nomination should consist of answers to the questions below. It can
be co-signed by several EATCS members. At least two nomination letters 
per candidate are recommended. If you are supporting the
nomination from within the candidate's field of
expertise, it is expected that you will be specific about the
individual's technical contributions.

To be considered, nominations for 2016 must be received by December 31, 2015.

1. Name of candidate
Candidate's current affiliation and position
Candidate's email address, postal address and phone number
Nominator(s) relationship to the candidate

2. Short summary of candidate's accomplishments (citation -- 25 words or less)

3. Candidate's accomplishments: Identify the most important
contributions that qualify the candidate for the rank of EATCS Fellow
according to the following two categories: 

A) Technical achievements
B) Outstanding service to the TCS community

Please limit your comments to at most three pages.

4. Nominator(s):
Affiliation(s), email and postal address(es), phone number(s)

Wednesday, September 30, 2015

Call for Nominations: Presburger Award for Young Scientists 2016

Presburger Award for Young Scientists 2016

   Call for Nominations

   Deadline: December 31st, 2015

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 Mojzesz 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 2016 the date of birth should be in 1980 or later). The Presburger Award Committee of 2016 consists of Zoltan Esik (Szeged), Marta Kwiatkowska (Oxford) and Claire Mathieu (Paris, 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:
   Claire Mathieu

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

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

Previous Winners:

   Mikołaj Bojanczyk, 2010
   Patricia Bouyer-Decitre, 2011
   Venkatesan Guruswami and Mihai Patrascu, 2012
   Erik Demaine, 2013
   David Woodruff, 2014
   Xi Chen, 2015

Official website:

Thursday, September 24, 2015

Gödel Prize 2016: Call for nominations

The Gödel Prize 2016 - Call for Nominations
Deadline: January 31, 2016

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery, Special Interest Group on Algorithms and Computation Theory (ACM SIGACT). The award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The 24th Gödel Prize will be awarded at the 43rd International Colloquium on Automata, Languages and Programming, 11-15 July 2016 in Rome, Italy.

The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before von Neumann’s death, in what has become the famous “P versus NP” question.

The Prize includes an award of USD 5,000.

Award Committee: The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT. The 2016 Award Committee consists of Moses Charikar (Stanford University), Orna Kupferman (Hebrew University), Kurt Mehlhorn (Max Planck Institute), Joseph Mitchell (State University of New York at Stony Brook), Andrew Pitts (chair, University of
Cambridge) and Madhu Sudan (Harvard University).

Eligibility: The 2016 Prize rules are given below and they supersede any different interpretation of the generic rule to be found on websites of both SIGACT and EATCS. Any research paper or series of papers by a single author or by a team of authors is deemed eligible if
  • the paper was published in a recognized refereed journal no later than December 31, 2015;
  • the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2003.
The research work nominated for the award should be in the area of theoretical computer science. Nominations are encouraged from the broadest spectrum of the theoretical computer science community so as to ensure that potential award winning papers are not overlooked. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.

Nominations: Nominations for the award should be submitted by email to the Award Committee Chair: Please make sure that the Subject line of all nominations and related messages begin with “Goedel Prize 2016.” To be considered, nominations for the 2016 Prize must be received by January 31, 2016.

Any member of the scientific community can make nominations. The Award Committee may actively solicit nominations. A nomination should contain a brief summary of the technical content of the paper(s) and a brief explanation of its significance. A printable copy of the research paper or papers should accompany the nomination. The nomination must state the date and venue of the first conference or workshop publication, or state that no such publication has occurred. The work may be in any language. However, if it is not in English, a more extended summary written in English should be enclosed. To be considered for the award, the paper or series of papers must be recommended by at least two individuals, either in the form of distinct nominations, or one nomination including recommendations from at least two different people. Additional recommendations may also be enclosed and are generally useful. The Award Committee encourages recommendation and support letters to be mailed separately, without being necessarily shared with the nominator(s).
The rest of the nomination package should be sent in a single email whenever possible. Those intending to submit a nomination should contact the Award Committee Chair by email well in advance. The Chair will answer questions about eligibility, encourage coordination among different nominators for the same paper(s), and also accept informal proposals of potential nominees or tentative offers to prepare formal nominations. The committee maintains a
database of past nominations for eligible papers, but fresh nominations for the same papers (especially if they highlight new evidence of impact) are always welcome.

Selection Process: The Award Committee is free to use any other sources of information in addition to the ones mentioned above. It may split the award among multiple papers, or declare no winner at all. All matters relating to the selection process left unspecified in this document are left to the discretion of the Award Committee.

All  winners since 1993 are listed at

Friday, September 18, 2015

EATCS Award 2016: Call for Nominations

The call for nominations for the EATCS Award 2016 is out. (You can find it below.)I strongly encourage the members of the TCS community to submit nominations. Our field is full of people who would richly deserve this accolade and writing a strong letter of nomination is one of the ways to show that we value their contributions to our field of science. Nominations from previous years will be considered automatically. 

The EATCS Award 2016

Call for Nominations

Deadline: December 31st, 2015

The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from our community with the prestigious EATCS Distinguished Achievement Award. The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.  For the EATCS Award 2016, candidates may be nominated to the Award Committee consisting of
  • Fedor Fomin (University of Bergen),
  • Kim Guldstrand Larsen (Aalborg University) and 
  • Jean-Éric Pin (CNRS and University Paris-Diderot).
Nominations will be kept strictly confidential. They should include supporting justification and be sent by e-mail to the chair of the EATCS Award Committee:

Kim Guldstrand Larsen

The list of previous recipients of the EATCS Award is at

The next award will be presented during ICALP 2016 in Rome, Italy.

Sunday, September 13, 2015

The ideal invited speaker

A colleague recently asked me whether I had any opinion on what an invited speaker at a conference should do to repay the confidence the PC chairs and the conference organizers placed in her/him. I do not have much experience on this matter myself, but, for what they are worth, here are my opinions, after having had a peek at the Platonic world of ideas under the voice "ideal invited speaker". (Caveat: I realize that what I write below is an ideal that is hard to reach in real life since we are all pressed for time and we all have a lot on our plates. However, as Salvador Dali said, one  should have no fear of perfection --- one will never reach it.)

Let's start with the most obvious role played by an invited speaker at a conference: an invited speaker should deliver a well polished and clear keynote address that is broadly accessible to the conference attendees. Fulfilling this goal requires a careful choice of the topic for the invited talk and preparation, as well as a rough idea of the profile of the typical conference attendees. Of course, some of the participants in the conference might not appreciate all the details of the material covered in the talk and some of it might be addressed to experts, but the talk should have a clear message and should give everyone in the audience something to take home. (I believe that this applies to every talk one gives, as Gian-Carlo Rota said in the first of his ten lessons he wished he had been taught.)

The delivery of a good talk is, however, by no means the only contribution that an invited speaker should give to a conference. In my book, an invited speaker should take active part in the conference. This means that (s)he should attend most, if not all, of the conference sessions (assuming the conference does not have parallel sessions, of course), ask questions as appropriate (and in particular, if no question is forthcoming from the rest of the audience), discuss with the conference participants during the breaks, mingle and take part in the social programme, and serve as an example for the young researchers in the audience.

This is hard work, but being an invited speaker is a great honour that comes with some responsibilities towards the PC chairs, the organizers and the community as a whole.

Friday, September 11, 2015

Italian Conference on TCS 2015

The 16th Italian Conference on Theoretical Computer Science (ICTCS 2015) finished today a little over 1pm Italian time. The event, which was held in Florence, was well organized by Pierluigi Crescenzi, Michele Loreti and Betti Venneri and gave a bird's eye view of some of the research in TCS in Italy.

As part of the event, the Italian Chapter of the EATCS handed out three prizes. The Young TCS Researcher Award went to Ugo Dal Lago (University of Bologna), who delivered an inspiring one-hour talk on Higher-Order Probabilistic Computation: Calculi, Observational Equivalence, and Implicit Complexity. The Doctoral Research Award was presented to Ornela Dardha (University of Glasgow) for her doctoral dissertation Type Systems for Distributed Programs: Components and Sessions, which she completed at the University of Bologna under the supervision of Davide Sangiorgi. For the first time, the Italian Chapter of the EATCS also gave prizes to two master theses in TCS.

One of the contributed papers, Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring, was authored by Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, and Björn Orri Sæmundsson, who just finished their bachelor studies at Reykjavik University.  I can't think of a better advertisement for my department of computer science and hope that the authors will have a great career, whatever they decide to do in the future.

Thanks to Betti, Michele and Pierluigi for having organized a scientifically interesting and socially pleasant conference.