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
   clairemmathieu@gmail.com

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: http://www.eatcs.org/index.php/presburger

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: Andrew.Pitts@cl.cam.ac.uk. 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 http://www.sigact.org/Prizes/Godel/.

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
Email: kgl@cs.aau.dk

The list of previous recipients of the EATCS Award is at

http://eatcs.org/index.php/eatcs-award

The next award will be presented during ICALP 2016 in Rome, Italy.

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.

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.

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.

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. 

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.

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.

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.

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.

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.

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.

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.

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

• Subhash Khot (New York, USA),
• Marta Z. Kwiatkowska (Oxford, UK),
• Xavier Leroy (INRIA, France) and
• Devavrat Shah (MIT, USA).

I will have more to say about future editions of the conference after the general assembly tomorrow.

Program for ICALP/LICS 2015

ICALP/LICS 2015 is approaching fast and the very final version of the program for this event is available here.

A look at the program indicates the very broad coverage of TCS provided by the event. Apart from the presentation of 204 contributed papers (143 for ICALP and 61 for LICS), we will be treated to the following plenary invited talks:

Ken-ichi Kawarabayashi (NII, Japan)
Title: Digraphs Structures: Minors and Algorithms

Daniel Kifer (Pennsylvania State University, USA)
Title: Privacy and the Price of Data

Valerie King (University of Victoria, Canada)
Title: Dynamic Graphs: Time, Space, and Communication

Thomas Moscibroda (Microsoft Research and Tsinghua University, China)
Title: Incentive Networks

Anca Muscholl (Université Bordeaux, France)
Title: Automated Synthesis of Distributed Controllers

Peter O'Hearn (Facebook and University College London, UK)
Title: From Categorical Logic to Facebook Engineering

Luke Ong (University of Oxford, UK)
Title: Higher-Order Model Checking: An Overview

ICALP/LICS will also feature the following three tutorials:

Piotr Indyk (MIT, USA)
Title: Fast Algorithms for Structured Sparsity

Andrew Pitts (University of Cambridge, UK)
Title: Names and Symmetry in Computer Science

Geoffrey Smith (Florida International University, USA)
Title: Recent Developments in Quantitative Information Flow

as well as a "masterclass" on Algorithms and Complexity for Japanese Puzzles by
Ryuhei Uehara (JAIST, Japan).

The joint award session  will feature presentations by Xi Chen (Presburger Award recipient), Christos Papdimitriou (EATCS Award recipient) and Igor Walukiewicz (LICS Test-of-Time award recipient). Christos will also reflect on 40 years of theoretical computer science during a special anniversary event devoted to the 40th birthday of the journal Theoretical Computer Science.

Note that ICALP 2015 and LICS 2015 are truly co-located events. The two conferences will take place in the same week and at the same location. There is only one registration fee and conference participants will be able to attend whatever session they fancy at either conference.

I look forward to this festival of TCS and hope to have enough energy to report on some of the events on this blog. (I am still looking for guest bloggers!)

Call for guest posts from ICALP 2015/LICS 2015

If you are going to ICALP 2015/LICS 2015 and you are willing to contribute guests posts on that conference on this blog, drop me a line.

It would be good to have reports on the three tracks of ICALP, on LICS, on the invited talks/tutorials and on the award-related events, as well as on the conference as a whole.

In case you are interested, the guests posts on ICALP 2014 contributed by Clément Canonne and Andrew Winslow are here.

PhD positions in Computer Science at IMT Lucca (Italy)

This is the time of the year when IMT Lucca announces a number of fully funded PhD scholarships. IMT Lucca is one of the institutions in Italy that is closest to my heart and where I have had the pleasure to spend some time in the past interacting with PhD students and faculty. It provides an excellent environment for PhD students in a truly splendid setting. I strongly recommend it, if you are considering a PhD in several areas of computer science and control theory. Watch the video below, which will whet your appetite, and then read on.



The Institute for Advanced Studies IMT Lucca - Italy invites applications for fully-funded PhD scholarships in Computer Science tenable from 1st November 2015.

IMT Lucca is a truly international research university within the Italian public higher education system that focuses on cutting-edge research in key areas such as Computer Sciences, Systems Engineering, Complex Networks, Economics and Cultural Heritage. The three-year doctoral program, which is taught entirely in English, is articulated in four discipline-specific curricula that share an interdisciplinary scientific background.

Computer Science doctoral studies at IMT are coordinated by Rocco De Nicola and promote research on the theory and applications of informatics such as concurrency, performance, programming languages, security, dependability, software engineering, and computational biology. The overarching goal is to develop languages, models, algorithms, verification techniques, engineering methodologies, and software tools for reasoning about distributed systems.

The doctoral students will be working within the SysMA research unit of IMT Lucca (http://sysma.lab.imtlucca.it/); some of the research lines are pursued in collaboration with two institutes of the Italian Research Council (CNR) in Pisa, namely ISTI (http://www.isti.cnr.it) and IIT (http://www.iit.cnr.it).

PhD students receive a stipend of about €13,600 EUR gross (around €12,400 EUR after taxes) per year, as established by Italian law. In addition, they are offered free meals and on-campus housing in the historical center of the beautiful Tuscan city of Lucca. Students also get the opportunity to spend research periods abroad, with the possibility of receiving additional financing through the Erasmus+ program.

The deadline for application is June 29th, 2015 at 18:00 Italian time.

The call is open to all candidates who are expected to obtain the required degree by October 31st, 2015; however, they must still apply by the above deadline. Further details, along with the online application form, can be found at: http://phd.imtlucca.it

ICALP 2015: Accepted papers and best paper awards

The PCs for the three tracks of ICALP 2015 have selected the best papers and best student papers. The best paper awards will go to the following articles:

• Aaron Bernstein and Clifford Stein. Fully Dynamic Matching in Bipartite Graphs. (Track A)
• Jarkko Kari and Michal Szabados. An Algebraic Geometric Approach to Nivat's Conjecture. (Track B)
• Yiannis Giannakopoulos and Elias Koutsoupias. Selling two goods optimally. (Track C)
     

The best student papers will instead go to

• Huacheng Yu. An Improved Combinatorial Algorithm for Boolean Matrix Multiplication. (Track A)
• Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. (Track A)
• Georg Zetzsche. An approach to computing downward closures. (Track B)

As you can see Track A selected two best student papers, whereas Track C did not select any. Let me remark that Radu Curticapean already received the best student paper award at ICALP 2013.

The full list of accepted papers for each of the tracks of ICALP 2015 is here. 

EATCS honours three outstanding PhD theses with the first EATCS Distinguished Dissertation Awards

The EATCS is proud to announce that, after examining the nominations received from our research community,  the EATCS Distinguished Dissertation Award Committee 2015, consisting of Javier Esparza, Fedor Fomin,  Luke Ong and Giuseppe Persiano (chair), has selected the following three theses for the EATCS Distinguished Dissertation Award for 2015:

• 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"

Each of the awards carries a monetary prize of 1000 Euros, provided by the EATCS. Each of the award-receiving dissertations will be published on line by the EATCS at http://www.eatcs.org/index.php/dissertation-award.

Karl Bringmann's thesis consists of two parts: one dealing with ``Sampling from Discrete Distributions'' and one dealing with ``Computing Fréchet Distances.'' Sampling from a discrete probability distribution is a fundamental and classically studied problem. Bringmann's thesis contributes a deeper understanding of the amount of memory needed for sampling from  a discrete  probability distribution. The provided bound is tight for systematic data structures and  for non-systematic data structures, the thesis shows that, quite surprisingly, with only 1 redundant bit it is possible to reply to queries in expected constant-time. In the second part  of the thesis, Bringmann relates the computational complexity of computing the Frechet distance of two curves (a classical notion from Computational Geometry) with a variant, SETH', of the Strong Exponential Time Hypothesis. Specifically, if SETH' holds, then the Frechet distance of two curves cannot be computed in time strongly subquadratic.

Skrzypczak’s thesis is about the use of descriptive set theory as a framework for investigating the omega-regular tree languages or equivalently the languages defined by formulas of Monadic Second Order logic with several successors. The thesis makes progress on long-standing open problems in the theory of automata: the characterizations of regular languages of infinite trees that are definable in weak monadic second-order logic and the Rabin-Mostowski index problem. For both problems, Skrzypczak's thesis provides solutions for notable special cases.

Wootters' thesis approaches coding-theoretic problems from an analytic point of view, rather than an algebraic point of view and develops new tools for studying codes, makes several contributions and settles a few important open problems. Specifically, Wootters' thesis advances the understanding of two important topics in Coding Theory: List Decoding and Local Seconding. Regarding List Decoding, the thesis shows that random linear codes, over constant-sized alphabets, are optimally list-decodable (this answers a question asked by Elias over twenty years ago) and that there exist Reed-Solomon codes which are list-decodable beyond the Johnson bound (this answers a question asked by Guruswami and Sudan over 15 years ago). Regarding Local Decoding, the thesis gives a family of high-rate codes with local correctability that admits a sublinear-time decoding algorithm.