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.

ICTAC goes to Cali, Colombia

The organizing committee of ICTAC 2015 has asked me to help them distribute the following CfP of the event. The International Colloquium on Theoretical Aspects of Computing (ICTAC) is going to Colombia this year. The list of invited speakers is superb and Colombia has been a good source of young talent in TCS in recent years. Consider supporting this event by submitting a paper to it.

**********************************************************************

               CALL FOR PAPERS -- ICTAC 2015
                 12th International Colloquium on 
                 Theoretical Aspects of Computing
               29-31 October 2015, Cali, Colombia
                      ** http://www.ictac2015.co **

DEADLINE FOR SUBMISSIONS: JUNE 5, 2015.
**********************************************************************


ICTAC 2015 will take place at the campus of Universidad Javeriana, Cali, Colombia during October 29-31, 2015.  The ICTAC conference series aims at bringing together practitioners and researchers to exchange ideas and experiences addressing challenges in theoretical aspects of computing as well as in exploiting theory through methods and tools for system development.  ICTAC also aims to promote cooperation between participants and institutions from developing and industrial countries in research and education.


THEMES AND TOPICS OF PAPERS
Topics of interest include theories of computation and programming, foundations of software engineering and formal techniques in software design and verification, as well as  tools that support formal techniques for software modeling, system design and verification.


The topical areas of the conference include, but are not limited to
*     Automata theory and formal languages;
*     Principles and semantics of programming languages;
*     Theories of concurrency, mobility and reconfiguration;
*     Logics and their applications;
*     Software architectures, their models, refinement and verification;
*     Relationship between software requirements, models and code;
*     Program static and dynamic analysis and verification;
*     Software specification, refinement, verification and testing;
*     Model checking and theorem proving;
*     Models of object and component systems;
*     Coordination and feature interaction;
*     Integration of theories, formal methods and tools for engineering computing systems;
*     Service-oriented architectures: models and development methods;
*     Models of concurrency, security, and mobility;
*     Theory of distributed, grid and cloud computing;
*     Real-time, embedded, hybrid and cyber-physical systems;
*     Type and category theory in computer science.


INVITED SPEAKERS 
* Jean-Raymond Abrial
* Volker Diekert
* César Muñoz
* Catuscia Palamidessi
* Davide Sangiorgi
* Moshe Vardi
* Glynn Winskel


ASSOCIATED EVENTS
* ICTAC Summer School on Formal Methods (October 25-27)
* DCM 2015: 11th International Workshop on Developments in Computational Models (October 28)


PAPER SUBMISSION
== Important Dates 
* Abstract submission: Monday, June 1, 2015.
* Paper submission:   Friday, June 5, 2015.
* Author notification:  Monday, July 20, 2015.
* Camera ready:  Monday, August 3, 2015.

CONCUR 2015 Deadline approaching

The deadline for CONCUR 2015 is approaching fast:

• Submission of Abstracts: April 13th, 2015;
• Submission of Papers: April 20th, 2015 (firm).

Note that you can submit your abstracts at any time before April 20. 

The usage of pdflatex and the LIPIcs style file are mandatory: no changes to font size, page geometry, etc. are permitted. Authors are invited to submit a draft of at most 13 pages including references. Submissions not in the correct format or submitted after the deadline will not be considered.

Ode to the Automata Tutor

I am slowly emerging from teaching a first year course on topics in Discrete Mathematics to about 250 students at Reykjavik University. (I have one more lecture to deliver after Easter and then the not-so-small matter of over 200 exam papers to grade :-() This is the second discrete mathematics course the students take and it is the second spring semester in a row that I teach it.

As part of the course, I am supposed to cover  the basics of grammars, finite automata and regular expressions. This is a first year course, so I do not cover much of the theory related to these formalisms and their connections. Mostly I expect the students to be able to design grammars, finite automata and regular expressions for some relatively simple languages.

In both editions of my course, which has been followed by about 500 students overall, I have used the AutomataTutor to support my teaching of material related to finite automata and to grade student assignments automatically.

For what it is worth, I strongly encourage my readers to try the tool and to use it in their undergraduate courses. In my experience, the students love to learn DFA and NFA programming using the Automata Tutor and to work on assignments that employ it. The automatic feedback and grading provided by the Automata Tutor are almost magical. (See this paper for a description of how the tool does both.) This is how the construction of finite automata that recognize regular languages should be taught in a modern way! I wish I had similar tools for all the topics I need to cover in that course.

From my perspective (and from that of my TAs), automatic grading is a real bonus. I love to teach, but I really hate to grade a large number of student assignments. Students can be very creative in their solutions and grading them is a very time consuming, haphazard and inconsistent process for any human. The algorithms embodied in the Automata Tutor produce consistent results at the press of a button and the students receive a grade straight away as well as excellent hints on how to improve incorrect solutions.

Thanks to Rajeev Alur, Loris D'Antoni, Sumit Gulwani, Dileep Kini, Mahesh Viswanathan and their co-workers, teaching basic finite-automata theory to hordes of first-year students can now (largely :-)) be done without tears. To boot, the folks at Automata Tutor have always been ready to provide technical help, when that was needed.

I'll keep using the Automata Tutor in my courses and I hope that you will do so too. That is the best way to thank our colleagues for the work they have done and are still doing on that tool.

February 2015 issue of the Bulletin of the EATCS on line

Thanks to the work of Kazuo Iwama, editor in chief of the bulletin, and of his collaborators, the February 2015 issue of the Bulletin of the EATCS is now available on line. You can download the whole issue in PDF from here, if you prefer. As a service to the TCS community, the bulletin continues being open access because of the support of the members of the EATCS, whom I thank wholeheartedly.

Amongst other things, this issue contains contributions by David Eppstein on K-Best Enumeration, Vikraman Arvind on Robust Oracle Machines revisited, Gaudi Taubenfeld on A Closer Look at Concurrent Data Structures and Algorithms (pages 59-82 of the whole issue), Jukka Suomela on Local Coordination and Symmetry Breaking ((pages 83-110 of the whole issue), Andreas Blass on Negative Probability and by Juraj Hromkovic who kicks off the new-look Education Column with a piece entitled Homo Informaticus.

I welcome Stefan Schmid as new editor of the Distributed Computing Column and thank Panagiota Fatourou for her sterling editorial work over many years.

Enjoy it. 

Video made by the female CS student association at Reykjavik University

I learnt a few things about some of the students taking the first-year course I am teaching right now by watching this well-made video.

EATCS Fellows class of 2015 named

The EATCS has recognized five of its members for their outstanding contributions to theoretical computer science by naming them as recipients of an EATCS fellowship.

The EATCS Fellows for 2015 are:

• Artur Czumaj (University of Warwick, United Kingdom) for "contributions to analysis and design of algorithms, especially to understanding the role of randomization in computer science";
• Mariangiola Dezani-Ciancaglini (Università di Torino, Italy) for "distinguished and seminal achievements in formal methods and foundations of programming languages, introducing or developing new type systems for the lambda-calculus as well as for the pi-calculus and related calculi";
• Thomas A. Henzinger (Institute of Science and Technology Austria) for "fundamental contributions to formal verification and synthesis of computer and biological systems";
• Dexter Kozen (Cornell University, USA) for "pioneering and seminal work in fields as diverse as  complexity theory, logics of programs, algebra, computer algebra and probabilistic semantics";
• Moshe Y. Vardi (Rice University, USA) for "fundamental and lasting contributions to the development of logic in computer science and exceptional services to the community of theoretical computer science."

The aforementioned members of the EATCS were selected by the EATCS Fellow Selection Committee, after examining the nominations received from our research community. The EATCS Fellow Selection Committee for 2015 consisted of

• Rocco De Nicola (IMT Lucca, Italy),
• Paul Goldberg (Oxford, UK),
• Anca Muscholl (Bordeaux, France),
• Dorothea Wagner (Karlsruhe, Germany; chair) and
• Roger Wattenhofer (ETH Zurich, CH).

The EATCS Fellows Program was established by the association  in 2014 to recognize outstanding EATCS members for their scientific achievements in the field of Theoretical Computer Science.

The EATCS is very proud to have the above-mentioned members of the organization among its fellows.

The list of EATCS Fellows is available at  http://www.eatcs.org/index.php/eatcs-fellows.