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:

• Karl Bringmann: "Sampling from Discrete Distributions and Computing Fréchet Distances"
• Michał Skrzypczak: "Descriptive set theoretic methods in automata theory"
• Mary Wootters: "Any errors in this dissertation are probably fixable: topics in probability and error-correcting codes"

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.