ICALP 2016 took place last week in Rome from the 12th till the 15th of July. The conference, which brought ICALP to Italy for the fifth time, was well organized by Tiziana Calamoneri, Irene Finocchi, Nicola Galesi and Daniele Gorla, whom I thank for the effort they put into making ICALP 2016 a memorable event.
According to the data presented by Tiziana on behalf of the local organizers during the General Assembly of the EATCS held on Thursday, 14 July, ICALP 2016 had 239 registered participants, 74 of which were students. The USA was the country contributing the largest share of attendees (50), followed by France, the UK, Germany and Italy. Let me note, in passing, that I would have expected a larger number of participants from Italy, given the size of the Italian TCS community, the number of TCS researchers based in Rome and in neighbouring cities, and the ease with which Rome can be reached from most of the country. (Italy contributed 21 participants to the conference.)
ICALP 2016 featured four invited talks, which were delivered by Devavrat Shah (MIT, USA), Xavier Leroy (INRIA, France), Seffi Naor (Technion, Israel) and Marta Z. Kwiatkowska (Oxford, UK), as well presentations by the recipients of the Presburger Award, the Gödel Prize and the EATCS Award.
Devavrat Shah kicked off the conference on Monday, 12 July, by delivering a talk entitled Computing Choice. In his talk, Devavrat discussed algorithmic results relating to ranking, rank aggregation and personalized rankings associating intensity to rankings based on partial information resulting from a sparse set of comparisons. The talk, which was excellently paced and interesting, presented many results and I invite you to check Dev's work for the details.This work addresses computational challenges for decision making without a choice model, and offered a glimpse of the exciting possibilities for inter-disciplinary work across disciplines such as CS, EE, OR and Economics.
Xavier Leroy delivered the second invited talk, entitled Formally verifying a compiler: What does it mean exactly?, on Wednesday, 13 July. In his talk, Xavier discussed the context for, and the results of, the CompCert project, which investigates the formal verification of realistic compilers usable for critical embedded software. Such verified compilers come with a mathematical, machine-checked proof that the generated executable code behaves exactly as prescribed by the semantics of the source program. In this project, Coq is used both as a proof assistant and as a programming language.
In his talk, Xavier said that "Pure functional programming is the shortest path to writing and verifying software." He also asked and addressed two fundamental questions arising from this work and related ones:
- Did we prove it (the compiler) right?
- Did we prove the right thing?
Seffi Naor's talk took place on Thursday, 14 July, and was entitled Maximatization of submodular functions: Recent progress. Seffi stepped in at the last moment for Subhash Khot, who was unable to make the trip to Rome. On behalf of the EATCS and of the TCS community as a whole, I thank him for delivering an excellent talk at such a short notice.
Research on the topic of Seffi's talk started in the 1950s-1960s and is now thriving. It has applications in the study of social welfare, economics/game theory, combinatorial optimization, machine learning and information theory. In his talk, Seffi first surveyed results on unconstrained maximization of non-monotone functions, with focus on approximation algorithms, and then presented results for the constrained maximization problem. I refer the readers to Seffi's papers and to this Wikipedia page for more information.
The last invited talk at ICALP 2016 was delivered by Marta Z. Kwiatkowska on Friday, 15 July. Marta's talk was entitled Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice and is accompanied by a paper that is available here. Marta stated right at the start that, despite the success that model checking and synthesis techniques have had and are having, we have not found yet the right modelling abstractions for autonomous mobile agents such as robots and autonomous vehicles. Software for these vehicles is expected to behave reliably under uncertainty, and its analysis and synthesis require quantitative approaches to specification and verification. As Marta argued cogently in her talk, a game-theoretic point of view is fruitful in the study of such systems. Indeed, games of various kinds have played a fundamental role in the study of the synthesis of correct programs from specifications from the very beginning, and papers on game-theoretic models abound in Volume B conferences. (See the slides for this talk by Moshe Vardi for historical remarks and an overview of the game-theoretic approach to synthesis.) Rather than attempting to summarize Marta's talk, I strongly encourage you to read her accompanying paper, which beautifully summarizes her work on this topic and contains pointers to related literature.
The core of the scientific programme consisted of the papers that were selected for presentation by the PC chairs (Michael Mitzenmacher, Yuval Rabani and Davide Sangiorgi) and their PCs. Because of EATCS commitments, I could not attend as many talks as I would have liked, but all those I did manage to listen to were excellent both scientifically and from the point of view of the quality of the presentation. (For one of the talks, I even had to wear 3D glasses :-)) Thanks to the PC chairs and their PCs for doing a truly great job!
The award ceremony was held on Wednesday, 13 July, and saw the presentation of the EATCS Distinguished Dissertation Awards, of the Presburger Award to Young Scientists, of the Gödel Prize and of the EATCS Award. The event was a festive occasion and celebrated some of the outstanding members of the TCS community.
The EATCS Distinguished Dissertation Award Committee, consisting of Javier Esparza, Michal Feldman, Fedor Fomin, Luke Ong and Giuseppe Persiano (chair), has selected the following three theses for the EATCS Distinguished Dissertation Award for 2015:
- Radu Curticapean, The Simple, Little and Slow Things Count: On Parameterized Counting Complexity. Thesis work carried out at the Department of Computer Science at Saarland University, Saarbrücken, Germany. Supervisor: Markus Bläser.
- Heng Guo. Complexity Classification of Exact and Approximate Counting Problems. Thesis work carried out at the Department: of Computer Sciences in the University of Wisconsin-Madison. Advisor: Jin-Yi Cai,
- Georg Zetzsche. Monoids as storage mechanisms. Thesis work carried out at the Department: of Computer Science at University of Kaiserslautern. Supervisor: Roland Meyer.
The Presburger Award was presented to Mark Braverman (Princeton University, USA). The Gödel Prize went to Stephen Brookes and Peter O'Hearn for their invention of concurrent separation logic, and the EATCS Award was given to Dexter Kozen. The presentation of each of these three awards was accompanied by an excellent talk by the award recipient(s). As I mentioned during the award ceremony, this might very well be the first time that the Gödel Prize is mentioned in a piece in the New Yorker.
The award session was extremely well attended and preceded a short bus tour in Rome and a social dinner in a popular restaurant in Trastevere.
The annual General Assembly of the EATCS took place on Thursday, 14 July. I'll report on it elsewhere. Here I will limit myself to saying that, at the General Assembly, I formally stepped down as president of the EATCS after two terms of service (four years). The new president of the EATCS will be Paul Spirakis (University of Liverpool and U. Patras). He will be supported by Leslie Ann Goldberg (University of Oxford), Antonin Kucera (Masaryk University) and Giuseppe Persiano (University of Salerno) as vice-presidents. At ICALP 2016 in Rome, Dirk Janssens also left his post as treasurer of the EATCS after 27 years of sterling service. Jean-Francois Raskin kindly accepted to serve as the new treasurer of our association. The association is very grateful to the above-mentioned colleagues for their willingness to serve and to Dirk for his outstanding service over such a long time. I know that the EATCS community will support the members of the new leadership in their work, just like they helped me during the last four years.
If you were at ICALP in Rome and you have any comment, suggestion or criticism, please post them as comments. I'll make sure that they reach the leadership of the EATCS. We are always working on improving an already very successful conference that does its best to provide a bird's eye view of TCS as a whole.
No comments:
Post a Comment