ICALP'98, the 25th conference in this series, was organized by BRICS, the centre for Basic Research in Computer Science, which is distributed between the Computer Science Departments of Aarhus and Aalborg. The conference itself was held in Aalborg, a modest-sized city near the northern tip of Denmark.
The conference had an impressive list of invited speakers: Martin Abadi, Gilles Brassard, Tom Henzinger, Mark Overmars, Andrew Pitts, Amir Pnueli, Leslie Valiant and Avi Wigderson. There was also a special lecture by the winner of this year's Godel Prize, Sensouke Toda.
Let me begin by discussing the invited talks in the order in which they were presented.
Amir Pnueli kicked off the conference with a talk on Verification of Linear Temporal Logic Specifications. The talk was on techniques for model-checking LTL assertions in transition systems whose transition relation is defined implicitly. As far as I could tell, there was nothing surprising in what he presented except for the complete lack of discussion of complexity-related issues.
In the afternoon, Mark Overmars spoke on Geometric Algorithms for Robotic Manipulation. He addressed applications of computational geometry in mechanized manufacturing---for instance, how best to anchor a part on an assembly line so that is does not slide or rotate when a hole is being drilled into it. Overmars pitched his talk at the right level for people not directly in the field (like myself). He described the algorithms behind the industrial applications clearly without going into pedantic proofs and provided a number of genuinely illustrative illustrations.
The best talk of the conference was Avi Wigderson's presentation on the second morning, Can probabilistic algorithms significantly outperform deterministic ones?. In a technically detailed but incredibly clear and concise talk, he established that two desirable results which one might want to establish:
Wigderson was followed in the afternoon by Andrew Pitts on Existential types: logical relations and operational equivalence. Those who follow this line of work told me that the talk was good, but perhaps not great. I personally did not get very far in understanding what he was talking about and switched off.
On Wednesday morning, Sensuoke Toda delivered the Godel Prize lecture. He spoke on proofs in complexity theory using operators---his lecture reminded me of proving trigonometric identities by desperately multiplying and dividing in order to massage a given formula into another one. The most entertaining aspect of the talk was his habit of putting down a transparency on one projector and then pointing, by mistake, to the other one.
Tom Henzinger spoke on Thursday morning on Model Checking Game Properties of Multi-agent systems. By multi-agent systems, he actually meant systems where some of the moves are made by an adverserial environment---a typical situation addressed in control theory. The talk was frequently interrupted by skeptics who drew his attention to earlier work in the area which his group had ignored, but Henzinger was unmoved and unrepentant.
Much was expected from Leslie Valiant's Thursday afternoon talk on A Neuroidal Architecture for Cognitive Computation. Unfortunately, his badly organized talk and his dry style of speaking left most of the audience very disappointed. Fortunately, he contributed a substantial write-up to the proceedings. There was a small minority of people who praised the talk---by and large, these people had read Valiant's recent well-received book entitled Circuits of the Mind, so perhaps one needed to do some homework to appreciate the talk.
I missed Gilles Brassard's invited talk on Friday morning, on Quantum Information Processing. I was told that the talk was excellent.
The last invited talk of the conference was by Martin Abadi, on Protection in programming-language translations. I could not make out much from the title. The talk turned out to be on how to theoretically model and analyse security issues in computer systems. I would have loved to have learnt more about this topic, but the presentation was very superficial. All I came away with was the fact that in Abadi's framework, security aspects are modelled using process calculi like the pi-calculus.
The technical sessions, as usual, were held in parallel. Though ICALP is a broad-spectrum conference, it tends to attract more papers in Logic and Semantics than in Algorithms and Complexity. As a result, some of the sessions---notably those pertaining to automata---had to be artificially categorized as Algorithms and Complexity, leading to some conflicts of interest among the participants. Among the talks I attended, the ones by Moshe Vardi and Jean-Eric Pin were probably the best.
ICALP began the day after the final of the Football World Cup in France, so the social events began with a big-screen presentation of the final with a complimentary bottle of beer to each participant. On Monday, there was a welcome-reception. The conference dinner was held on Wednesday in a forest, preceded by a long walk through the forest where the organizers has planted fake ``robbers'' to surprise the participants. On Thursday evening there was an excursion to an ancient Viking burial ground near Aalborg. A rival attraction was a football match amongst the participants on the grounds adjacent to the conference venue.
Without exception, I missed all these events because I preferred to stay with friends in Aarhus and commmute 100~km up and down to attend ICALP. An unexpected bonus of this otherwise awkward arrangement was that the weather in Aarhus was much better than the weather in Aalborg, which was almost always cold, windy and wet, though it was the height of summer.
I also missed the EATCS business meeting on Tuesday evening. One of the main attractions of the meeting was the presentation of the Godel prize. There was also a debate on whether to discontinue ICALP as a single broad-spectrum theory conference and instead make it a collective name to describe a group of specialized conferences, along the lines of the federated conferences organized by IEEE and ACM. This radical proposal was shot down by a sizeable majority, though the young Turks in favour of the reorganization are hopeful that they will have their way eventually, once the old guard retires from active combat.
Associated with ICALP were four satellite workshops. The first, abbreviated Sttt (the S is for Software and one of the T's is for Tools, I believe) was held on Sunday, before the conference. The other three, Approx'98 (approximation algorithms), Infinity'98 (infinite-state systems) and Soap'98 (semantics of objects as processes) were held on the weekend after the conference.
I attended Infinity'98, largely because I could not fly back to India from Copenhagen before Saturday night. (Also, when the ICALP programme came out, I discovered that I had been working in this area without being aware of it---our paper was scheduled for presentation in a session entitled Infinite State Systems!).
There were three invited talks, by Bengt Jonsson (good), Philippe Schnoebelen (interesting but arcane) and Bernhard Steffen (muddled and confusing), in addition to five contributed presentations. I was hoping to come away from the workshop with some unifying ideas underlying the analysis of infinite-state systems but, alas, I was disappointed. I believe that Infinity will not be held next year, perhaps with good reason.
I must mention the coverage of the conference in the local media. The local newspaper carried a news item on how the ``world's smartest'' people had gathered at ICALP. Devdatt Dubhashi was pointed out by the organizers as one of the ``smart people'' who had come from far away to attend the conference, carefully disguising the fact that he just happened to be there in his capacity as a regular visitor at BRICS, and could thus be relied upon to not say anything negative about the organizers. The net result was that Devdatt's photograph made it to the next day's edition of the paper.
Finally, a word about the organization. Everything went off smoothly and a generally pleasant time was had by all, inspite of the atrocious weather.