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 http://bulletin.eatcs.org/index.php/beatcs/issue/view/18

You can download a pdf with the printed version of the bulletin from http://www.eatcs.org/images/bulletin/beatcs116.pdf. 

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.