Friday, October 17, 2014

First CFP for ICALP 2015

The first call for papers for ICALP 2015, which will be held in Kyoto in the period 6-10 July 2015, is available here.

I hope that you will consider submitting your best work to the conference. The event will be rich of scientific events and will be co-located with LICS 2015. To whet your appetite, here is the list of invited speakers and invited tutorials:

Invited Speakers

Ken Kawarabayashi, NII, Japan
Valerie King, University of Victoria, Canada
Thomas Moscibroda, MSR Asia, China
Anca Muscholl, University of Bordeaux, France (Joint with LICS)
Peter O'Hearn, Facebook, UK (Joint with LICS)

Invited Tutorial Speakers (Joint with LICS) 

Piotr Indyk, MIT, USA
Andrew Pitts, University of Cambridge, UK
Geoffrey Smith, Florida International University, USA

Masterclass speaker 

Ryuhei Uehara, JAIST, Japan

Wednesday, October 08, 2014

CFP for CCC'15 posted

Dieter van Melkebeek has informed me that the CFP for CCC'15 has just been posted. The direct link is

The deadline for submissions is November 26, 2014.

I hope that members of the CCC community will submit some of their best work to the first edition of the conference with open-access proceedings published in LIPIcs

Saturday, October 04, 2014

Call for nominations: EATCS Award 2015

Please consider nominating outstanding theoretical computer scientists for the EATCS Award 2015. 
The EATCS Award 2015

Call for Nominations

Deadline: December 31st, 2014

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 2015, candidates may be nominated to the Award Committee consisting of
  • Fedor Fomin (University of Bergen),
  • Kim Guldstrand Larsen (Aalborg University) and 
  • Vladimiro Sassone (University of Southampton).
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:

Vladimiro Sassone

The list of previous recipients of the EATCS Award is at

The next award will be presented during ICALP 2015 in Kyoto, Japan.

Friday, October 03, 2014

Letter from the President of the EATCS for the October issue of the Bulletin

In case any of my two readers is interested in having a look, here is the letter from the president that will appear in the October issue of the Bulletin of the EATCS.

Dear colleagues,

First of all, I hope that you had a good summer break and that you have recharged your batteries for whatever challenges await you in the new academic year.

For many of us, the start of each academic year is accompanied by teaching courses to new cohorts of students. Computer Science enrollments seem to be increasing all over the world and several institutions, including mine, will have to decide how to handle the large number of students who are eager to enter our degree courses. I encourage you to have a look at the slides available here for an American perspective on computer science enrollments. Look also at this Harvard Crimson article. Course CS 50 at Harvard has over 800 undergraduates (and over 850 total) signed up, making it now the largest class at Harvard.

Having many students is, of course, a substantial amount of work, but the popularity of computer science also gives us a very good opportunity to entice  some of these students to study the theory of computing; let's make the most of it!

I enjoyed meeting several of you at ICALP 2014 in Copenhagen. It was a pleasure to see many young researchers and students at the conference, and I really appreciated the good attendance we had at the event. Thanks to all of you who made the trip to Copenhagen!

The 41st ICALP was an excellent conference, both scientifically and socially. The organizers did their very best to make it a memorable event, and I like to think that all the participants felt welcome and enjoyed the conference. On behalf of the EATCS, I warmly thank Thore Husfeldt and his team for doing an outstanding job.

You can read my report on ICALP 2014 in this issue of the Bulletin. The recordings of the invited talks and of the award session are available from the conference web page. I hope that you will watch them.

ICALP 2015 will be held in Kyoto, Japan, and will be co-located with LICS 2015. Kazuo Iwama is the ICALP 2015 general chair. After 42 years, this will be the first ever ICALP outside Europe and I am very excited at the prospect of holding ICALP in Japan. I hope that you will make plans to submit your best papers to the conference. The call for papers for the conference will be ready for distribution soon.

The general assembly of the EATCS decided that ICALP 2016 will be held in Rome, Italy. I thank Tiziana Calamoneri and her collaborators for their willingness to host us in Rome.

One of the important decisions that the Council of the EATCS will have to make over the next few months is related to the future publication outlet for the proceedings of ICALP from 2016. Our current contract with Springer will expire at the end of 2015, but we only have until March 2015 to negotiate any changes to it or to decide whether to move to a different publication outlet. I look forward to hearing any opinion you might have on this matter.

Regarding publications, I strongly encourage all the members of the EATCS to make all their publications freely accessible on line. It is our duty, as well as being in the interests of our science and in our own interest, to make access to our scientific work free of financial barriers for any researcher. This is possible even for papers that have appeared in journals and conference proceedings published by commercial publishers.

As usual at this time of the year, the EATCS issues calls for nominations for the EATCS Award, EATCS Fellows and the Presburger Award. (The call for the Gödel Prize will be published at a later time, when ACM SIGACT has named its representatives in the prize committee.) You can read the calls in this issue of the Bulletin; they have also been posted on mailing lists, blogs and social networks. Please distribute the calls as you see fit. Most importantly, I hope that you will take the time to nominate excellent researchers and papers for these awards. Awards and prizes are a way to recognize the achievement of some of our many outstanding colleagues and they put our favourite research fields in the spotlight. Last, but by no means least, awards provide examples and inspiration for the younger generations of researchers who are the future of our field as a whole. Writing a nomination takes some of our precious time, but it is worth it.

At the time of writing, the EATCS is cooperating with the newly formed ACM SIGLOG, the EACSL and the Kurt Gödel Society on a new award, which we hope to be in a position to announce in the not-too-distant future. I am also happy to announce that the Computational Complexity Conference will be held in cooperation with the EATCS from 2015.

On Thursday, 2 October, I attended a talk given at my university by Donald Sadoway, John F. Elliott Professor of Materials Chemistry at the Massachusetts Institute of Technology. His talk was inspirational and stressed the importance of research carried out at universities the world over. University research is even more fundamental today than it ever was because, according to Sadoway, universities are the places where truly innovative research takes place. In his view, corporate research laboratories do not embark in fundamental research today as they did in the past.

While listening to Sadoway's talk, I could not help but think about the sudden closure of Microsoft Research Silicon Valley. As you all know, Microsoft Research Silicon Valley had achieved a very high reputation within the theoretical-computer-science community because of the scientific standing of its stellar staff, the high impact of the work done at the laboratory, the mentoring role its members played within our research community (with many outstanding
young researchers spending important formative periods at the laboratory) and its stimulating research environment with frequent visits by high-profile scientists.

As the blog posts from TCS researchers and the associated comments clearly
indicate, losing Microsoft Research Silicon Valley has left our community with a sense of loss and sadness, also because of the timing and the abrupt nature of its closing.

With a laboratory like Microsoft Research Silicon Valley, Microsoft had gained a substantial amount of credence within the theoretical-computer-science community and had attracted some of the best talent in our field worldwide. Many outstanding young researchers had considered a position at Microsoft Research Silicon Valley and Microsoft's other research labs as their first choice, even above tenure-track or tenured positions at prestigious academic institutions. All this is now probably bound to change, which would be a loss for both Microsoft and our research community.

For what it is worth, I hope that Microsoft Research will continue to support research in theoretical computer science. Advances in the theory of computing will benefit the company in the long run and further investments by Microsoft in TCS will be beneficial for our field of study.

I thank you for reading this letter, and look forward to hearing suggestions and opinions from the members of the EATCS (and the community at large). You are the heart and soul of our association!

Wednesday, September 17, 2014

Call for nominations: Presburger Award 2015

Here is the call for nominations for one of the EATCS awards that is closest to my heart. Do put pen to paper and nominate your favourite young TCS researcher! He/She might join a truly impressive list of previous award recipients.
Presburger Award for Young Scientists 2015

   Call for Nominations

   Deadline: December 31st, 2014

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 2015 the date of birth should be in 1979 or later). The Presburger Award Committee of 2015 consists of Zoltan Esik (Szeged), Claire Mathieu (Paris), and Peter Widmayer (Zürich, 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:

   Peter Widmayer

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

The award includes an amount of 1000 Euro and an invitation to ICALP 2015 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
Official website:

Thursday, September 11, 2014

Call for Nominations: EATCS Distinguished Dissertation Award 2014

The EATCS has established the EATCS Distinguished Dissertation Award to promote and recognize outstanding dissertations in the field of Theoretical Computer Science.

Any PhD dissertation in the field of Theoretical Computer Science that has been successfully defended in 2014 is eligible.

Three dissertations will be selected by the committee for year 2014. 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 with subject EATCS Distinguished Dissertation Award 2014 by 31 December 2014. 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 additional endorsement letters.

The dissertations will be selected by the following committee:
  • Javier Esparza
  • Fedor Fomin
  • Luke Ong
  • Giuseppe Persiano
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.

Monday, September 08, 2014

Report of TRENDS 2014 (Guest post by Ilaria Castellani and MohammadReza Mousavi)

Ilaria Castellani and MohammadReza Mousavi have kindly written this guest post reporting on TRENDS 2014, a satellite event of CONCUR 2014 organized by IFIP WG1.8 on Concurrency Theory. Enjoy it!

TRENDS 2014 is the third edition of the series of workshops organized by the IFIP Working Group 1.8 on Concurrency Theory. TRENDS traditionally comprises invited speeches by both promising young researchers and leading senior researchers to demonstrate the emerging trends in concurrency theory research. The workshop is followed by the business meeting of the working group, which is open to the public. This year's TRENDS was attended by 20 participants throughout the workshop and featured 4 excellent talks by the following first class speakers:
  1. Alexandra Silva gave an introduction to using co-algebras as a generic way of exploiting efficient algorithms in automata theory for minimization and equivalence checking of labelled transition systems (or different variants thereof) with respect to various notions of behavioural equivalence. In particular, she showed how Brzozowski's algorithm for minimization of finite automata can be used to minimize LTS's efficiently and also how Hopcroft and Karp's algorithm for checking language equivalence can be used to check equivalence of LTS's with respect to different notions of behavioural equivalence. She also presented some ideas about the application of learning algorithms for automata in the domain of concurrency theory. She concluded her talk by the following motto: Co-algebra is not only about semantics, but also about algorithms. Alexandra's slides are here.
  2. Simon Gay gave an overview of the history of session types and in particular remembered the legacy of the late Kohei Honda as the founding father of this field. He then pointed subsequent important developments in the field, such as the introduction of behavioural sub-typing by himself and the link to linear logic and the very interesting recent interpretation of the Curry-Howard isomorphism in the concurrency theory setting by Luís Caires, Frank Pfenning and associates. He also gave an overview of the future challenges in this field.
  3. Michele Bugliesi, who has recently been appointed as the Rector of the University of Venice, pinpointed security vulnerabilities in the current practice of authentication. Then, he presented the solutions devised by him and his associates through client-side protection of authentication cookies. The devised techniques were formally shown to guarantee security (provide authentication and integrity) on a formalization of the Firefox browser. The proof techniques use a noninterference-like notion, which exemplifies yet another application of concurrency theory.
  4. Stéphanie Delaune gave a presentation on the formal modelling and analysis of cryptographic protocols. She used a privacy issue in the old French electronic passport as a motivating example and showed how process algebraic formalisms, such as the applied pi-calculus, can be used in modelling the protocols used in such an e-passport (at an abstract level) and how behavioural equivalences (equipped with additional term equivalences on terms) can be used to verify these protocols. She pointed out several existing tools for this purpose, also developed within her group at ENS Cachan, and presented the challenges in her ongoing research.