Thursday, December 31, 2015

EC comes to Europe

The EC'16 conference will be held in lovely Maastricht, NL next year with Vincent Conitzer as general chair. As far as I can tell, this is the second time that EC comes to Europe in its 17-year history. This is a step that, as president of the EATCS, I warmly welcome.

Submit your best work to EC'16 and you'll have a chance to visit a historical city at the heart of Europe to boot!

Monday, December 28, 2015

Four EATCS Awards with deadline for nominations on the 31st of December 2015

This is to remind you that the deadline for nominations for the following awards is the 31st of December 2015:

    EATCS Award:
    EATCS Distinguished Dissertation Award:
    EATCS Fellows:
    Presburger Award:

I strongly encourage members of the TCS community to nominate eligible colleagues for these accolades. Writing a good letter of nominations takes a little work, but  this is time well spent as it puts some of the many outstanding members of our community and their research areas in the spotlight, and provides role models for the younger members of the TCS community.

Call for nominations for the 2016 Alonzo Church Award

It's been a long journey, but the Alonzo Church Award is finally off the ground. Here is the call for nominations I just received from the first award committee. You will notice that the deadline for nominating papers for the first award is close: March 1, 2016.  (Of course, the call for nominations will be issued earlier next year.) For the time being, I hope that you will follow Littlewood's zero-infinity law: If you  have a paper (or papers) you'd like to nominate for the award, do it now, where in this case "now" means "by the end of February 2016" :-)

The award committee, whose members I thank on behalf of the EATCS, look forward to receiving your nominations!

The 2016 Alonzo Church Award


Outstanding Contributions to Logic and Computation

Call for Nominations


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

Eligibility and Nominations

The contribution must have appeared in a paper or papers published within the past 25 years. Thus, for the 2016 award, the cut-off date is January 1, 1991. 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 2016 award are now being solicited. The nominating letter must summarize 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 are due by March 1, 2016, and should be submitted to

Presentation of the Award

The 2016 award will be presented at LICS, the flagship conference of SIGLOG. 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 2016 Alonzo Church Award Committee consists of the following four members: Catuscia Palamidessi, Gordon Plotkin, Wolfgang Thomas, and Moshe Vardi (chair).

Monday, December 21, 2015

The 'novelty' of arXiv overlay journals

Last September, Nature published an article on a new publishing initiative by Timothy Gowers. The Nature piece starts thus:
"New journals spring up with overwhelming, almost tiresome, frequency these days. But Discrete Analysis is different. This journal is online only — but it will contain no papers. Rather, it will provide links to mathematics papers hosted on the preprint server arXiv. Researchers will submit their papers directly from arXiv to the journal, which will evaluate them by conventional peer review."
and ends as follows:
"The question, perhaps, is how readily researchers will embrace the model. “Apart from being an arXiv overlay journal, our journal is very conventional, which I think is important so that mathematicians won't feel it is too risky to publish in it,” says Gowers. “But if the model becomes widespread, then I personally would very much like to see more-radical ideas tried out as well” — for example, post-publication review and non-anonymous referees."
Based on the first paragraph of this blog post by Timothy Gowers, it is highly likely that Discrete Analysis will start by publishing some very strong papers. This will probably play an important role in enticing mathematicians to publish some of their best work in it and in giving the new journal a good impact factor within a reasonable amount of time.

However, as mentioned in the Nature piece and as Gowers himself pointed out in his blog post announcing Discrete Analysis, arXiv overlay journals are not new. In TCS, Logical Methods in Computer Science published its first issue ten years ago and has become one of the favourite publication outlets for researchers working on logic in computer science, broadly construed. Logical Methods in Computer Science is an open-access journal, covered by Thompson ISI , SCOPUS, DBLP, Mathematical Reviews and Zentralblatt. (Impact factor: 0.443.) All journal content is licensed under a Creative Commons license.

Moreover, the 'arXiv overlay principle' is also used by Electronic Proceedings in Theoretical Computer Science (EPTCS), an international refereed open access venue for the rapid electronic publication of the proceedings of workshops and conferences, and of Festschriften, etc, in the general area of theoretical computer science, broadly construed. This proceedings series, which was initiated in 2008-2009 by the sterling effort of Rob van Glabbeek, has published 200 volumes at the time of writing this blog post. (Congrats to EPTCS for reaching the milestone of 200 volumes!)

Just like Discrete Analysis will do, Logical Methods in Computer Science (and EPTCS for workshops and conferences) only publishes papers that have undergone classic peer review and have been vetted for publication by the cognizant editor. For what it is worth, I therefore fail to see why Logical Methods in Computer Science and Discrete Analysis, once it starts publishing papers, are not doing journal publishing, as hinted in this excerpt from a post from the scholarly kitchen:
"My view is that while this is a fascinating way to draw out from arXiv links to good preprints in relevant fields, this is not journal publishing. In Gower’s blog he moves on from talking about the idea of the overlay journal to a more polemical discussion of how his venture is in essence the future of the journal, reducing costs and supplying quality content in a way that may be used in the same way journal articles are used now. While Gowers has every right to his views on this, I would argue that, while his is certainly an exciting way to make use of preprints in arXiv, what it does is quite distinct from a journal. As discussed above, the journal is a matter of record, and like it or not, journals form a part of the academic and recognition workflow that allows for career progress, grant making, more research and more articles to be published."
Logical Methods in Computer Science is "a matter of record", and publishing in it does carry weight in hiring and promotion decisions. Prime conferences in the field, such as LICS, have used it for their special issues.

Whether a journal publishes its contents as overlay of the arXiv or by some other means, IMHO it is the process that went into selecting the papers and the scientific quality of what is published that matter.

Tuesday, December 08, 2015

EATCS Awards 2016: Deadline approaching!

This is to remind you that the deadline for nominations for the following EATCS awards is the 31st of December 2015:

EATCS Award:
EATCS Distinguished Dissertation Award:
EATCS Fellows:
Presburger Award:

I strongly encourage members of the TCS community to nominate eligible colleagues for these accolades. Writing a good letter of nominations takes a little work, but this is time well spent as it puts some of the many outstanding members of our community and their research areas in the spotlight, and provides role models for the younger members of the TCS community.

The deadline for nominations for the Gödel Prize ( is January 31, 2016.

The award committees for the above-mentioned prizes and honours look forward to receiving your nominations!

Tuesday, December 01, 2015

Logarithms in the cultural pages of an Italian newspaper

Last Saturday, the cultural pages of a major Italian newspaper featured an article with the title "Arte digitale - la creatività salvata da social e logaritmi" ("Digital art - creativity saved by social networks and logarithms", sic) . The article ends with the following war cry: un "logaritmo vi seppellirà" oppure un "logaritmo vi salverà! " (a logarithm will bury you or a logarithm will save you!).

Well, after all, "logarithm" is an anagram of "algorithm" :-)

Friday, November 27, 2015

Whence Algorithmic Game Theory?

I recently saw the slides for the invited talk delivered by Moshe Vardi at SR 2015, the third International Workshop on Strategic Reasoning, which was held in Oxford in the period 21-22 September 2015. The talk was entitled A Revisionist History of Algorithmic Game Theory and must have stimulated some discussion at the workshop.

Moshe's message was that algorithmic game theory is older than the "official history" would make one believe and that
The most important message, however, is that one should tear down the wall between Vol. A and Vol. B. As readers of this blog may have realized, this is a message to which I wholeheartedly subscribe, perhaps because in the small research community I live in, we have to go to each other's talks to even have an audience at all.

Tuesday, November 17, 2015

Call for Workshops Proposals affiliated with ICALP 2016

Irene Finocchi asked me to distribute the appended call for workshop proposals for ICALP 2016. If you plan to organize a TCS workshop, why not co-locating it with that conference in Rome? The workshop chair is Nicola Galesi.

Call for Workshops Proposals affiliated with ICALP 2016
July 11-15, 2016,  Rome, Italy

Workshop proposals are solicited for ICALP 2016. A workshop may relate to any of the three tracks of ICALP, but proposals related to all aspects of theoretical computer science will be considered as well.

ICALP workshops typically feature a number of invited speakers and a number of contributed presentations.  Workshops will be held on the first day of the conference (July 11, 2016) and will have a duration of at most one day.

Workshop proposals should be no longer than two pages and should include:
- title of the workshop;
- person(s) responsible for the workshop (name and email address);
- a short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the ICALP community;
- the proposed format and agenda;
- procedures for selecting participants and papers;
- expected number of participants.

Proposals should be sent in pdf format to

Important dates
Submission due: December 20, 2015
Notifications: January 10, 2016
Final program due: 15 May 15, 2016

Further information

We provide the following aspects of the workshop organisation:
- registration;
- wireless network, conference rooms, etc. (as for ICALP);
- a link to the web page of the workshop;
- local support and organization.

We do not provide:
- management of any scientific aspects of the workshop program (the workshop organizers are responsible for call for papers, call for participation, notification, program, workshop webpage, publication of workshop proceedings or journal special issues, etc.);
- publicity for the workshop.

Tuesday, November 03, 2015

PC chairs for ICALP 2017

I am happy to inform you that the PC chairs for ICALP 2017, which will be held in Warsaw, Poland, in the period 10-14 July 2017 will be:
The conference chairs will be Mikolaj Bojanczyk and Piotr Sankowski.

On behalf of the EATCS, I thank these colleagues for their willingness to serve.

Sunday, October 25, 2015

27th Nordic Workshop on Programming Theory

The 27th Nordic Workshop on Programming Theory (NWPT 2015) was held at Reykjavik University in the period 21-23 October and was organized by AnnaIngolfsdottir and me in cooperation with our postdocs  Dario Della Monica, Ignacio Fabregas and Alvaro Garcia Perez. It finished on Friday, 23 October,  at around 17:30 after three packed days of scientific presentations.

The workshop had 57 registered participants (50 of which came from abroad, giving yet another indication of the powerful lure of Iceland as a destination for scientific events), and several talks were also attended by some local faculty members and students who were not officially registered for the workshop. All sessions had a good audience, including the very last one.

The workshop was graced by three excellent invited talks and the quality of the contributed presentations was consistently high. It was very pleasing to see many young researchers deliver clear, well prepared and well paced presentations. You can find all the abstracts for the contributed presentations and the slides for nearly all the talks here.

The invited talks were delivered by Rocco De Nicola (IMT Lucca, IT), Marta Kwiatkowska (University of Oxford, UK) and Jiri Srba; (Aalborg University, DK).

Rocco kicked off the workshop with a talk entitled Languages and Models for Collective Adaptive Systems (slides). Collective Adaptive Systems are heterogeneous collections of autonomous task-oriented systems that cooperate on common goals forming a collective system. Such systems consist of massive numbers of components that interact in complex ways amongst themselves and with other systems; they operate in open and non-deterministic environments, dynamically adapting to new requirements, technologies and environmental conditions. Developing such systems poses challenges to the developers such as the sheer number of components, the need to adapt to changing environments and requirements, the emergent behaviour resulting from complex interactions and the uncertainty both at design-time and at run-time. In his talk, Rocco presented the SCEL language developed by his research group for programming collective adaptive systems and its underlying theory.

Jiri delivered the Thursday invited talk on  Techniques and Tools for thefl Analysis of Timed Workflows (slides). According to Wikipedia, a work flow consists of an orchestrated and repeatable pattern of business activity enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. Many such workflows have strong real-time requirements, and their modelling and analysis is a significant challenge.

In his talk, Jiri suggested a workflow model based on timed-arc Petri nets and introduced the foundational problems of soundness and strong (time-bounded) soundness. He addressed the decidability of these problems and showed, among other results, that soundness is decidable for monotonic workflow nets while reachability is undecidable. For general timed-arc workflow nets, soundness and strong soundness become undecidable, though one can design efficient verification algorithms for the practically interesting subclass of bounded nets. Finally, he demonstrated the usability of the theory by presenting case studies dealing with a Brake System Control Unit used in aircraft certification, the MPEG2 encoding algorithm, a blood transfusion workflow and a home automation system for a family house.

The implementation of the algorithms is freely available as a part of the model checker TAPAAL, which I encourage you to try

Last, but not least, Marta delivered  an invited  talk on Computing Reliably with Molecular Walkers (slides). DNA computing is emerging as a versatile technology that promises a vast range of applications, including biosensing, drug delivery and synthetic biology. DNA logic circuits can be achieved in solution using strand displacement reactions, or by decision-making molecular robots, so called 'walkers', that traverse tracks placed on DNA 'origami' tiles. (See, for instance, Luca Cardelli's work.) Similarly to conventional silicon technologies, ensuring fault-free DNA circuit designs is challenging, with the difficulty compounded by the inherent unreliability of the DNA technology and lack of scientific understanding. In her talk, Marta gave an accessible  overview of computational models that capture DNA walker computation and demonstrated the role of quantitative verification and synthesis in ensuring the reliability of such systems. Since stochasticity is an essential component of DNA computing, not surprisingly Marta and her collaborators use the tool PRISM, whose development has been led by Marta herself, in modelling and analysis of molecular programs.

Marta and her co-workers applied quantitative modelling, verification and synthesis to three DNA case studies:
  1. DNA tranducer gate design (with Luca Cardelli),
  2. DNA walker design (with AndrewTurberfield's lab) and
  3. DNA origami dimer (also with AndrewTurberfield's lab).
All were continuous-time Markov chain models, and the first two were modelled analyzed successfully in PRISM. The third proved to be beyond the current capabilities of the tool. If you are interested, you will find papers on those case studies on Marta's publication page.

The workshop also had some local impact. In 
particular, several members of our association of female students in computer science met with Marta Kwiatkowska, Hanne Riis Nielson and 
other female participants to discuss about CS in an informal setting and learn from successful female role models, apart from those at their own institution. We thank these female 
colleagues for their mentoring role.

All in all, it seems to me that NWPT is excellent health and that many workshops, even with published proceedings, can only dream of having the type of support and environment that NWPT boasts.(The NWPT is an informal workshop without published proceedings, but there will be a special issue of a journal to which we will invite some selected contributions.)

The next edition of the workshop will be held in Aalborg. So the workshop will come back to Denmark, where it has not been held since 2009.

Wednesday, October 21, 2015

October 2015 issue of the Bulletin of the EATCS

The 117th issue of the EATCS Bulletin is now available online at

You can download a pdf with the printed version of the Bulletin from this link. 

As is customary for October issues of the Bulletin, this volume includes reports from ICALP 2015 and calls for nomination for EATCS Awards.

The contributions to the BEATCS columns are all interesting as usual. Let me just limit myself to mentioning that the contribution to the Concurrency Column by Ornela Dardha celebrates the prize she received for the Best Italian Dissertation in TCS in 2014. Fans of the Automata Tutor like me will want to read  the piece written by some of the prime movers behind the development of that wonderful tool.

Readers of this post might also be interested in the article Fast Algorithms for Structured Sparsity by Chinmay Hegde, Piotr Indyk and Ludwig Schmidt, which reports on the work on which the ICALP 2015 tutorial by Piotr was based. 

Thanks to Kazuo Iwama, the editor in chief of the BEATCS, the column editors, the colleagues who contributed to this issue of the Bulletin and Efi Chita from the EATCS Secretary Office for their wonderful work.

I hope that you'll enjoy this issue. I think that it is the duty of a scientific association like the EATCS to make its bulletin freely available to the TCS community. However, this would be impossible without the support from the members of the EATCS, whom I thank wholeheartedly.

Tuesday, October 20, 2015

CFP: 15th Scandinavian Symposium and Workshops on Algorithm Theory

This event is taking place at Reykjavik University in June 2016. Consider submitting!


SWAT 2016 - Call for Papers

15th Scandinavian Symposium and Workshops on Algorithm Theory
June 22-24, 2016, Reykjavik, Iceland

Submission deadline: Feb 14, 2016


The symposium, which alternates with the Algorithms and Data Structures
Symposium (WADS), is a forum for researchers in the area of design and
analysis of algorithms and data structures. We invite submissions of
papers presenting original research on algorithms and data structures.
Though we welcome experiments, the theoretical results in the articles
will be the main measure for evaluating their merits. Algorithmic
approaches of interest include, but are not limited to: approximation
algorithms, parametrized algorithms, distributed algorithms, parallel
algorithms, external-memory algorithms, data structures, exponential
time algorithms, online algorithms, randomized algorithms, streaming
algorithms, sub-linear algorithms. The algorithmic problems considered
may be motivated by applications, e.g. in optimization, geometry and
topology, graph analysis, bioinformatics, visualization, string
processing, information retrieval, machine learning, algorithmic game
theory, or mechanism design.


Contributors must submit their papers using the Easychair system.
Submissions should be in LIPIcs format (without font size, margin, or
line spacing changes), and not exceed 12 pages including front page and
references. See
for instructions. Additionally, if full details of proofs do not fit
into the page limit, a clearly marked appendix containing the remaining
details must be included; this appendix will not be regarded as part of
the submission and will be considered only at the discretion of the
program committee. Submissions deviating substantially from this format
risk rejection without consideration of their merits.

Papers submitted for review should represent original, previously
unpublished work. At the time the paper is submitted to the symposium,
and for the entire review period, the paper (or essentially the same
paper) must not be under review by any other conference with published
proceedings or by a scientific journal. However, we encourage authors to
make a preprint of their paper available at a public repository such as
arXiv. At least one author of every accepted paper is expected to register
and present the paper at the symposium. Symposium proceedings will be
published in the "Leibniz International Proceedings in Informatics"
(LIPIcs) series.


Submission deadline: Feb 14, 2016
Author notification: Early April, 2016
Symposium: Feb 17-20, 2016


A prize will be awarded to the author(s) of the best student-authored
paper. A paper is eligible if all of its authors are full-time students
at the time of submission. This must be indicated in the submission


 - Christian Sohler, Technische Universität Dortmund
 - Christian Wulff-Nilsen, University of Copenhagen
 - Dimitris Fotakis, National Technical University of Athens
 - Djamal Belazzougui, University of Helsinki
 - Ely Porat, Bar-Ilan University
 - Fabio Vandin, University of Padova
 - Faith Ellen, University of Toronto
 - Francois Le Gall, University of Tokyo
 - Gerhard Woeginger, Eindhoven University of Technology
 - Gonzalo Navarro, University of Chile
 - Kasper Green Larsen, Aarhus University
 - Marek Karpinski, University of Bonn
 - Marina Papatriantafilou, Chalmers University of Technology and Göteborg University
 - Nodari Sitchinava, University of Hawaii, Manoa
 - Ola Svensson, École Polytechnique Fédérale de Lausanne
 - Petteri Kaski, Aalto University
 - Pinar Heggernes, University of Bergen
 - Rasmus Pagh (chair), IT University of Copenhagen
 - Rob van Stee, University of Leicester
 - Seth Pettie, University of Michigan
 - Stefan Langerman, Université libre de Bruxelles
 - Suresh Venkatasubramanian, University of Utah
 - Therese Biedl, University of Waterloo


 - Christian Konrad, Reykjavík University
 - Magnús M. Halldórsson, Reykjavík University (chair)
 - Páll Melsted, University of Iceland
 - Tigran Tonoyan, Reykjavík University


 - Andrzej Lingas, Lund University
 - Esko Ukkonen, University of Helsinki
 - Jan Arne Telle, University of Bergen
 - Lars Arge, Aarhus University
 - Magnús M. Halldórsson, Reykjavík University


 -  (general information)

Wednesday, October 14, 2015

The EATCS Distinguished Dissertation Awards 2015: Call for Nominations

The EATCS has established the Distinguished Dissertation Award to promote and recognize outstanding dissertations in the field of Theoretical Computer Science. Any PhD dissertation in the fi eld of Theoretical Computer Science that has been successfully defended in 2015 is eligible.

Three dissertations will be selected by the committee for year 2015. The dissertations will be evaluated on the basis of originality and potential impact on their respective fields and on Theoretical Computer Science.

Each of the selected dissertations will receive a prize of 1000 Euro. The award receiving dissertations will be published on the EATCS web site, where all the EATCS Distinguished Dissertations will be collected.

The dissertation must be submitted by the author as an attachment to an email message sent to the address by December 31st, 2015 with subject EATCS Distinguished Dissertation Award 2015. The body of the message must specify:
  • Name and email address of the candidate;
  • Title of the dissertation;
  • Department that has awarded the PhD and denomination of the PhD program;
  • Name and email address of the thesis supervisor;
  • Date of the successful defence of the thesis.
A five page abstract of the dissertation and a letter by the thesis supervisor certifying that the thesis has been successfully defended must also be included. In addition, the author must include an endorsement letter from the thesis supervisor and can include one more endorsement letters.

The dissertations will be selected by the following committee:
  • Javier Esparza (Munich, Germany)
  • Michal Feldman (Tel Aviv, Israel)
  • Fedor Fomin (Bergen, Norway)
  • Luke Ong (Oxford, United Kingdom)
  • Giuseppe Persiano (Salerno, Italy)
The award committee will solicit the opinion of members of the research community as appropriate.

Theses supervised by members of the selection committee are not eligible.

The EATCS is committed to equal opportunities, and welcomes submissions of outstanding theses from all authors.

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.

Thursday, August 27, 2015

CONCUR 2015 Proceedings in LIPIcs

The proceedings of CONCUR'15 have now been published as volume 42 of LIPIcs and are available here.

This is the first edition of CONCUR with open-access proceedings: every reader will be able to access each paper free of charge from now on.

Monday, July 20, 2015

ICALP 2015: EATCS General Assembly

The annual EATCS General Assembly took place at ICALP 2015 in Kyoto from 17:30 till 19:00 on July 2015. The LICS 2015 business meeting took place at the same time, which meant that the number of participants at both meetings was not as high as it would have been normally.

I kicked off the meeting by honouring the memory of Jiří Matoušek (1963–2015), a true giant of Discrete Mathematics and TCS who also happened to have strong ties with the Japanese TCS community.

This was followed by a report from the local organizers (delivered by Kazuo Iwama) and by the PC chairs (delivered by Bettina Speckmann, who chaired the PC for Track A). During her presentation, Bettina made a personal observation related to the lack of "applied papers" at ICALP and suggested that this might be a new candidate for track C of the conference. This proposal was discussed a little, but did not get much support.

The organization for ICALP 2016, which will take place in the period 11-15 July 2016 in Rome, is going well and the preliminary CFP was ready for distribution in Kyoto. I presented the report from the conference organizers and was able to announce the invited speakers for the conference.

ICALP 2017 will be held in Warsaw, Poland. The proposed dates are July 10-14, 2017. The local chairs will be Mikolaj Bojanczyk and Piotr Sankowski.

Next I had a discussion with the participants related to the future of ICALP. In particular, I asked the following questions:
  • Does ICALP cover TCS sufficiently broadly?
  • What do you think of the current acceptance rates at ICALP?
  • Would you like to see 20-minute presentation slots with 15 minutes for presenting the paper (possibly leading to more slots and the acceptance of more papers)?
  • What would you like to see at ICALP that we don’t do?
  • Any criticisms/kudos/suggestions?
Based on the feedback I received from the audience in Kyoto, ICALP attendees seem to be fairly happy with the coverage of TCS the conference provides. They think that the current acceptance rates and the 25-minute presentation slots are fine.

I welcome feedback on any of the above points. The EATCS is here to serve the community (that is, you)!

At this point, I had to go and present a bid to hold LICS 2017 in Reykjavik, so the general assembly continued without me for a while.

Tony Kucera reported on the the EATCS Young Researcher Schools. The Second EATCS Young Researcher School, Understanding Complexity and Concurrency through Topology of Data, will be held in the period 13–22 July in Camerino, Italy, organized by Emanuela Merelli. Feel free to contact Tony if you have proposals for future schools.

Next, Kazuo Iwama delivered his report as editor in chief of the Bulletin of the EATCS.  I think that the Bulletin is going well under Kazuo's energetic and expert editorship. However, we do not rest on our laurels and there is always room for improvement.
  • What do you think of the current content of the BEATCS?
  • What kind of regular columns would you like to see?
  • What type of contributions should we solicit?

If you have any criticisms/kudos/suggestions please contact Kazuo and/or me.

The reports from the treasurer and the secretary of the EATCS reflected the good shape the EATCS is in these days. I thanked Ioannis Chatzigiannakis,  Efi Chita and Dirk Janssens for the great work they do for the EATCS.

After the summer break, we will electing 10 new members to the Council of the EATCS. The list of nominees so far, organized by country, is as follows:
  • Austria: Monika Henzinger
  • Denmark/Sweden: Thore Husfeldt
  • Finland: Jarkko Kari, Jukka Suomela
  • France: Anca Muscholl
  • Germany: Ulrich Meyer, Thomas Schwentick
  • Hungary: Zoltan Esik
  • Iceland: Magnus Halldorsson
  • Israel: Boaz Patt-Shamir
  • Netherlands: Jos Baeten, Gerhard Woeginger
  • Norway: Fedor Fomin
  • Spain: Elvira Mayordomo
  • Switzerland: Roger Wattenhofer
You are still on time to nominate colleagues for the election, which will start towards the end of August. You can do so by sending an email to secretary office and to me. 

I concluded the general assembly with my ritual report from the president on recent activities of the EATCS. You can find the details in my slides. Here I will limit myself to posting the questions I asked the participants in the general assembly in Kyoto.
  • What should the EATCS do for the TCS community?
  • What activities should the EATCS support (financially or otherwise)?
  • How can we make EATCS membership more attractive (especially among the younger generations)?
  • In the short term, what do you want me to try and achieve in the second year of my second term as president of the EATCS?
I am genuinely interested in your opinions. You are the life and blood of the EATCS, and the EATCS is here to serve the community. 

Friday, July 17, 2015

ICALP/LICS 2015: Christos Papadimitriou on 40 years of TCS

As part of a session devoted to the 40th anniversary of TCS (the journal) and just before the conference dinner, Christos Papadimitriou delivered a talk entitled 40 Years of TCS (the field). The talk was very interesting and inspirational. Since I trust that its content might be of interest to some of the readers of this blog, and to the community in general, I'll devote this post to summarizing the main point made by Christos in his presentation.

Christos started off by saying that in the early 1970s, ICALP was right on the money since TCS was roughly equivalent to Languages, Automata and Programs. At that time, 
  • P vs NP was, as Christos put it, an "obscure recent conjecture";
  • Compilers and the “semantics problem” were the topics that any young researcher who wanted to have impact and secure fame should work on;
  • Relational databases were under the horizon; and 
  • TCS owned CS, in the sense that the responsibility and main mission of TCS researchers was to outfit all areas of CS with rigour and the power of mathematics,  that TCS researchers of that time knew all of CS and exercised complete intellectual hegemony over the rest of CS. 
However, in those times CS was a second class citizen in the society of scientific fields.

Over the next twenty years, CS was an insecure and introverted field. However, with crucial help from TCS, it made progress on some great and difficult engineering problems such as compilers, databases, chips, OS, networks, software and parallelism to name but a few. Along the way, fast algorithms for some tough engineering problems were developed, the great importance of P vs NP became clearer as CS flooded the planet with IT. In Christos' opinion, CS grew tremendously in prestige because of these three reasons (that is, tough engineering problems, flooded the planet, P vs NP).

During those twenty years, TCS gave rigorous machinery for the engineering problems and scouted for depth.

That was also the time during which the split between TCS A and TCS B research occurred in North America. In his talk, Christos recounted the story of STOC 1985 in Providence, Rhode Island, during which all the accepted Vol. B papers were put in a single session (in which  his students Cosmadakis and Kanellakis had a paper) and an excursion to Newport Beach was organized at the same time!  After that, he said that Vol. B papers were basically not submitted any more to STOC/FOCS. 

Then the internet happened and deeply changed CS, which became extroverted, a natural science and a social science. TCS changed too, as it moved towards mathematics and opened up to the other sciences by applying the algorithmic lens to study their fundamental problems. In his talk, Christos mentioned the following examples of areas to which the algorithmic lens has been applied:
  • Statistical mechanics and phase transitions
  • Quantum computation
  • Economics and game theory
  • Evolution
  • The study of the brain. 
In his talk, he focussed on the study of evolution and the brain.

The theory of evolution is a brilliant theory for which a deluge of data is available. However, most important questions remain unanswered: Why is there so much genetic diversity? What is the role of sex/recombination? Is Evolution optimizing anything?

Christos pointed a surprising connection between evolution and game theory that he explored in this paper with Chastain, Livnat and U. Vazirani. The short story is that evolution of a population is a repeated game between genes, the strategies of each gene are its alleles, the common utility is the organism's fitness and the genes update their probabilities of play through multiplicative updates.

Moving to the study of the brain, Christos started by pointing out some great disconnects in our knowledge of the brain:
  • Babies vs computers (why is it that babies can easily achieve cognitive tasks that are very hard for computers? Addendum: According to Clement's recollection, Christos also asked why is it that "computers can easily achieve cognitive tasks that are very hard for babies"?)
  • Clever algorithms vs what happens in cortex
  • Understanding Brain anatomy and function vs understanding the emergence of the Mind
  • No known “neurally plausible” algorithm solving a nontrivial problem
  • Plus, disruptive insights such as downward traffic, reciprocity and clustering, prediction.
He forcefully stated that computer scientists should work on those problems. Indeed, Valiant has done work on the brain since 1995, pointing out that theory is essential and proposing the neuroidal model and vicinal algorithms. In the paper Cortical Learning via Prediction with Santosh Vempala (to appear at COLT 2015), Christos has studied a version of Valiant's Join primitive, called the Predictive Join (Pjoin), and proved that, in a precise technical sense, it solves the unsupervised learning problem.

Christos said that the PJoin and the PLink primitives seem to be useful for learning grammar and so a natural next step in his research is to tackle the problem of the emergence of language. His hypothesis is that language evolved in order  to exploit the strengths of the brain.

Christos closed his talk with a tantalizing question: What if the Mind emerges from rudimentary primitives, massive hardware and our brain's interaction with the very interesting environment provided by our planet?

This was a fitting finale to a wonderful story, devoted to a fascinating subject (TCS) and recounted by one of the true intellectual giants of our discipline.

Disclaimer: Any infelicity and inaccuracy in this report is solely my responsibility.

Thursday, July 16, 2015

ICALP/LICS 2015: Award session

The joint ICALP/LICS 2015 award session took place on Wednesday, 8 July, at the end of the scientific programme for the day. In keeping with the true co-location of the two conferences, it was fitting to hold a joint award session and to mix the award presentations. However, since ICALP had special sessions for the best papers, in order to keep the length of the award session sufficiently short, the ICALP best paper awards were handed out during the conference programme.

The session started with the presentation of the Presbuger Award 2015 to Xi Chen.  In his talk, Xi covered work in algorithmic game theory and computational economics related to the  computational complexity of Nash equilibria for various kinds of games.

Next, the Kleene Award for Best Student Paper was presented to Fabian Rieter (Université Paris Diderot) for his paper Distributed Graph Automata. It is remarkable that Fabian received this award for a paper based on work that he did for his MSc thesis in Freiburg. He is now a first-year PhD student in Paris.

The focus on student achievement continued with the mention of the three theses that received the first EATCS Distinguished Dissertation Award for 2014:
Michał Skrzypczak was present to receive the award certificate in person.

The LICS Test-of-Time Award went to Igor Walukiewicz (CNRS & Université Bordeaux-1) for his paper Completeness of Kozen's Axiomatisation of the Propositional mu-Calculus. In that paper, Igor settled a major open problem in the theory of the modal mu-calculus, namely that of the completeness of a deductive system proposed by Dexter Kozen in 1983.

In his acceptance talk, Igor gave an excellent overview of the history of the problem and of the ingredients that went into his solution to it. He also paid tribute to the wonderful research environment at BRICS, where his work was finalized.  That research centre, which was richly supported by the Danish National Research Foundation for 12 years together with its PhD school, made a huge difference for research in TCS in Denmark (and, I dare say, on a global scale) and some of its ripples (see also here amongst others) are still being felt today.

Last, but by no means least, Christos Papadimitriou delivered his acceptance speech for the EATCS Award 2015. In his entertaining and inspirational talk, Christos gave us an overview of his career and of the key developments in his work over the years, pointing out that, even though the EATCS award is given "to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career",  he still plans to continue working for a while, or at least until 2041 :-)

Christos started by talking about the early days, the influence of his parents and what it meant to grow up in a dictatorship. He conveyed to us the excitement of discovering the beautiful field of theoretical computer science during his doctoral studies at Princeton and then told us about his jobs. About his very productive (and stressful) period at MIT, he said that it took five years off his life expectancy. Christos also recounted to us a conversation he had with Paul Erdös at AT&T just before his move back to Polytechnio, his alma mater in Greece. Apparently, Erdös asked him: "Are you going back to the university that sacked Constantin Carathéodory or to the university that sacked name of another great Greek mathematician of the 20th century?" During his talk, Christos said that, as it turned out, he was going to the university that will sack Papadimitriou!

He surveyed the fields of CS from which the problems he has worked on stemmed, including
  • Algorithms and complexity for combinatorial optimization
  • Relational theory and concurrency
  • Logic and logic priogramming
  • Control theory, AI, robotics
  • Online and approximation algorithms, parallel algorithms and VLSI
  • The Internet
and he conveyed to us the excitement of the "Lens", thinking algorithmically about the great problems of science.

In his talk, Christos sang the praises of Berkeley and California, where he plans to be until 2041, of his teachers and his students (especially those who have been both), of the field of theoretical computer science as a whole (namely, the mathematical study of computation) and of his community. He described the TCS community as consisting of clever, interesting, strange, competitive, open, generous and fun people, who value elegance, relevance, originality, position in the field’s tradition and program, slogging/machinery, playfulness and humour.

Christos expressed his view that the current fragmentation in TCS (volume A vs volume B, Europe vs USA) is regrettable (and reversible).

He closed his talk by paying tribute to his co-authors (including 29 students, one multi-billionaire who makes his co-authors very rich on average, the 13 he has never met, the 27 Greeks and the one and only Mihalis Yannakakis, amongst others).

Christos also delivered another inspirational talk on 40 years of TCS (the field) at the 40th anniversary of the journal TCS, but that will have to be the topic for another post.

Sunday, July 12, 2015

June issue of the BEATCS out

I am happy to inform you that the June 2015 of the EATCS Bulletin, is now available online at

You can download a pdf with the printed version of the bulletin from 

Once more, thanks to the work of Kazuo Iwama, the editor in chief of the BEATCS, of the column editors and of the authors, this issue of the BEATCS is brimming with interesting content.

I thank all the members of the EATCS, whose small but important financial support (30 € per year and 30 € for two years for students) make it possible for us to have the BEATCS accessible to all the members of the TCS community.

Saturday, July 11, 2015

ICALP/LICS 2015: Day 5

The last day of ICALP/LICS 2015 took place yesterday. It started with the last invited talk of the event, which was delivered by Thomas Moscibroda (Microsoft Research and Tsinghua University, China). Thomas talked about Incentive Networks. The setting of his talk was as follows. In a basic economic system, each participant receives a (financial) reward according to his own contribution to the system.  For instance, the coffee retailers I do business with in Reykjavik typically give me a fresh drink every ten I buy. In his talk, Thomas, started by covering work on incentive trees and then moved on to his recent work on incentive networks.  In such networks, a participant’s reward depends not only on his own contribution; but also in part on the contributions made by his social contacts or friends. Thomas argued that the key parameter affecting the efficiency of such an Incentive Network based economic system is the participant’s degree of directed altruism, namely the extent to which someone is willing to work if her work results in a payment to her friend, rather than to herself. He also presented results on the impact of the network topology and other parameters on the efficiency of incentive networks.

The work by Thomas and his co-workers suggests that in many practical settings, Incentive Network-based reward systems might be more efficient than the ubiquitous ’pay-for-your-contribution schemes.

Thomas is an excellent speaker and his talk was accessible and gave the audience something to take home. The only complaint one could possibly have is that he went over time, thus leaving little time for questions and eating some precious coffee-break time before the last session of contributed talks. However, this was a small price to pay for having the chance to learn about an interesting topic I knew nothing about.

Overall, I think that the co-located ICALP/LICS 2015 was a resounding success. I thank the conference organizers for the great work in organizing this event and for allowing the ICALP and LICS communities to congregate in Kyoto for this event. This was the first ICALP outside of Europe and the first LICS in Asia.

If you were at ICALP/LICS and you have any comment/criticism/suggestion, please post a comment or send me an email. We are always keen to improve.

Thursday, July 09, 2015

ICALP/LICS 2015: Day 4

Day four at ICALP/LICS 2014 was kicked off by Anca Muscholl (Université Bordeaux, France), who delivered a talk entitled Automated Synthesis of Distributed Controllers. Anca's talk dealt with the problem of developing distributed monitors and distributed controllers for distributed programs. She argued that these problems can be fruitfully and naturally studied in the setting of Mazurkiewicz traces, using sharpened and specialized variations on Zielonka's celebrated theorem to synthesize monitors and controllers. Anca and her co-workers are working on turning Zielonka's construction into a practical method for distributed synthesis in specific settings of interest in the analysis of concurrent programs. I look forward to seeing the future developments in this work. For the moment, I enjoyed Anca's lucid and extremely well-paced presentation.

The afternoon session saw  Ryuhei Uehara (JAIST, Japan) deliverd an ICALP Masterclass on Algorithms and Complexity for Japanese Puzzles. In a very entertaining presentation, Ryuhei took us on a tour of games as a model for computation that started with Conway's Game of Life and Pebble Games and led us to some open problems in the complexity-theoretic analysis of games.

Ryuhei presented his own view on the complexity of games.
  • NP-complete puzzles are typically one player puzzles in which "something decreases at each step". 
  • PSPACE-complete puzzles are two player versions of NP-complete ones. 
He then introduced sliding block puzzles, which he claimed were open for a while until Hearn and Demaine introduced constraint logic as a general tool to study the complexity of games---see, for instance, this paper, which was fittingly published at ICALP 2002. (Caveat: as Ryuhei admitted during question time in reply to a question of mine, RUSH-HOUR was already known to be PSPACE-complete. However, as pointed out by Bob Hearn in a comment to this post, RUSH-HOUR is a constrained sliding-block puzzle. The complexity of general sliding-block puzzles, e.g. as described by Gardner in 1964, was still open after Rush Hour was shown PSPACE-complete. In his talk, Ryuhei did mention Martin Gardner's quote to the effect that "These puzzles are very much in want of a theory." For an excellent introduction to the work by Bob and Erik on the complexity of sliding-block puzzles, see the article by Bob Hearn available here.)

Finally, Ryuhei discussed the complexity of reconfiguration games, using the 15 puzzle and its generalizations as a motivating example.

The talk was very well attended and entertaining.

The scientific programme for the day closed with the event for the 40th anniversary of TCS, which featured an excellent presentation by Christos Papadimitriou on 40 years of TCS (the field). As usual, Christos delivered an entertaining and thought-provoking talk. I hope to find the time and energy to report briefly on it soon.

Wednesday, July 08, 2015

ICALP/LICS 2015: Day 3

The third day at ICALP/LICS 2015 was kicked off by a joint ICALP/LICS keynote address delivered by Peter O'Hearn (Facebook and University College London, UK). Peter's talk was entitled From Categorical Logic to Facebook Engineering and described at a high level of abstraction how his work on logic, categories and types led to the development of separation logic and of the algorithmic techniques that his colleagues and he embodied in tools that are now being deployed daily on the Facebook code base.

Peter presented a prime example of tools and techniques from the TCS community that have become mature enough to make a difference for the development of fast-changing code bases like the one at Facebook. Peter took us on a journey that covered a number of concepts from the computer science logician's toolkit, such as categorical logic and model theory, denotational semantics, the Curry-Howard isomorphism, Substructural Logic, Hoare Logic and Separation Logic, abstract interpretation, compositional program analysis, the frame problem, and abductive inference.

His talk was followed by the largest number of questions I have seen asked so far at this conference.

In the afternoon, I attended an ICALP and LICS joint tutorial delivered by Andrew Pitts (University of Cambridge, UK). Andy's tutorial dealt with a very interesting and hot topic, namely Names and Symmetry in Computer Science, a topic to which Andy has devoted a lot of research over the last few years, some of which is covered in this book. I invite you to consult these slides for an idea of what Andy's tutorial covered.

The day ended with a very eventful and inspirational joint award ceremony with talks by Xi Chen (Presburger Award recipient), Igor Walukiewicz (LICS Test-of-Time award recipient) and Christos Papadimitriou (EATCS Award recipient). I will try to write something about that session at some point tomorrow.

Tuesday, July 07, 2015

ICALP/LICS 2015: Day 2

The second day of ICALP/LICS 2015 was kicked off by Daniel Kifer (Pennsylvania State University, USA) who delivered a talk entitled  Privacy and the Price of Data. Actually, Daniel renamed his talk on the fly into "assigning numbers to data queries" (or "assigning number to things"). The talk surveyed work motivated from the observation that data is increasingly being bought and sold on the web and that this leads to query-based pricing that is customized for buyers. A key question addressed by the research of authors such as Koutris et al. at the University of Washington and by Daniel and his co-workers is what are the properties that a good pricing function for queries should have. In his talk, Daniel gave us an overview of such properties and how they relate to issues such as privacy. I  encourage any interested reader to browse his recent papers and the work by Koutris et al. at the University of Washington for the interesting details.

In the second invited talk of the day, Valerie King (University of Victoria, Canada) told us about Dynamic Graphs: Time, Space, and Communication.  Valerie's talk was organized around seven ideas in connectivity. She started from the classic union-find data structure and led us all the way to the seventh idea, namely the XOR method and sub-linear space from her SODA 2013 paper. (Valerie told us that she got the idea for that paper in Kyoto.) Work by Tarjan, Even, Fredrickson, Thorup and several other researchers featured prominently in her entertaining and accessible talk.

I do not have time to report on the EATCS general assembly now, but I will write a report on that meeting for the EATCS Bulletin at some point soon. For the moment, I will limit myself to saying that ICALP 2017 will be held in Warsaw, Poland. The proposed dates are July 10-14, 2017. The local chairs will be Mikolaj Bojanczyk and Piotr Sankowski.

At the ICALP 2017 business meeting, the bid by my wife and me to organize LICS 2017 in Reykjavik 2017 was approved. So LICS 2017 will he at Reykjavik University in the period 19-23 June 2017. Start sharpening your pencils now.

Monday, July 06, 2015

ICALP/LICS 2015: Day 1

Despite my jet-lag induced drowsiness and the fact that the clock on my laptop kept reminding that I was chairing the first meeting of the EATCS Council at around 4am in the morning, I enjoyed the first day of the conference a lot.

According to the organizers, ICALP/LICS 2015 had 400 early registrations and there were 200 people who attended the pre-conference workshops.The plenary invited talks by Ken-ichi Kawarabayashi (NII, Japan) and Luke Ong (University of Oxford, UK) were delivered to a packed room and were both excellent.

Ken-ichi's talk was entitled Digraphs Structures: Minors and Algorithms and presented his joint work with Stephan Kreutzer on extending results on minors from graphs to digraphs. (See this paper in particular.)

Luke's talk was devoted to Higher-Order Model Checking: An Overview. Higher-order model checking is about checking whether trees generated by recursion schemes satisfy formulae that can be expressed in some kind of logic, such as Monadic Second Order logic. In his talk, Luke surveyed the considerable progress on this problem in both theory and practice that has been made over the past fifteen years or so.

There were lots interesting talks in the conference programs as well as two sessions devoted to the best paper award recipients.

The busy day ended socially on a high note with an excellent welcome reception.

Looking at the future, I am pleased to inform you that the invited speakers for ICALP 2016 will be
I will have more to say about future editions of the conference after the general assembly tomorrow.