Friday, October 31, 2014

October 2014 issue of the Bulletin of the EATCS

The October issue of the EATCS Bulletin is now available online at from where you can access the individual contributions separately.

You can download a pdf with the printed version of the whole issue from

The Bulletin of the EATCS is open access, so people who are not members of the EATCS can read it. Let me thank the members of the association who make this service of the community possible with their support.  (EATCS members have access to the member area, which contains news and related articles and provides access to the Springer Reading Room. Young researchers can find announcements of open positions, news and related articles.)

This issue of the bulletin is brimming with interesting content, with five EATCS Columns and a piece by David Woodruff surveying the work for which he had received the EATCS Presburger Award 2014 amongst others. You might also enjoy reading the transcript of a dialogue between Christian Calude and Kurt Mehlhorn about theory, LEDA and Algorithm Engineering. I find it inspiring to read Christian's dialogues with famous members of our community and I always learn something useful from them. (Unfortunately, the lessons I think I learn do not make it often into my work practices. That's the theory-practice divide, I guess :-))

Here are a couple of excerpts to whet your appetite.
  • Kurt's motto, even definition, for Algorithm Engineering is: "Treat programs as first class citizens in algorithms research and not as an afterthought." He also adds that "Algorithm engineering is not only a sub-discipline of algorithms research. More importantly, it is a mind set."
  • CC: How do you manage to juggle between so many jobs in di fferent countries?
    KM: I try to follow some simple principles.
    I avoid multi-tasking. I set aside time for particular tasks and then concentrate on them. For example, when I was writing my 1984 books and the LEDA book, I would work on the book every work day from 8:00 am to 12:00 pm. I would not accept phone calls or interruptions by students during this time. Now, the 8am to 12pm slot is reserved for reading, thinking and writing. The no-interruption rule still holds.
    I clean my desk completely every evening when I leave my o ffice, so that I can start with an empty desk the next morning.
    When I accept a new responsibility, I decide, what I am going to give up for
    it. For example, when I became vice-president of the Max Planck Society in 2002 (for a 6 year term), I resigned as editor of Algorithmica, Information and Computation, SIAM Journal of Computing, Journal of Discrete and Computational Geometry, International Journal of Computational Geometry and Applications, and Computing.
    And most importantly, I am supported by many people in what I do, in particular, my co-workers, my students, and then administrative staff in the institute and the department. Cooperation and delegation are very important.
Enjoy the issue and consider contributing to future ones!

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!