ICALP 2012: Days 3-5

At long last, here are some of my notes from the main events that took place during the last three days of ICALP 2012. There were several excellent talks at Track B (which is the one I attended) and I hope to find the time to discuss some of my favourite papers at some point.

Day 3 was given the best of starts by Gilles Dowek's invited talk entitled A theory independent Curry-de Bruijn-Howard isomorphism. (The slides are here and the abstract is here.) IMHO, Gilles pitched his talk at precisely the right level for a general conference in TCS like ICALP and my impression was that he gave each attendee something to take home, regardless of their area of expertise.

Gilles introduced the seminal Curry-de Bruijn-Howard isomorphism, which was in fact originally proposed by Brouwer, Heyting, and Kolmogorov, who suggested to de fine constructive proofs as algorithms. He surveyed the principles behind the plethora of existing proof processing systems and the principles that led to the development of the universal proof checker Dedukti. Oversimpliying, Dedukti is based on what Gilles called Hilbert and Ackermann’s paradise: one logic and many theories. The logic is the lambda-Pi-calculus proposed by Harper, Honsell and Plotkin. However, theories are represented using rewrite systems, rather than using axioms. Indeed, according to Gilles, "Axioms suck!" (from the point of view of efficiency).

Overall, I enjoyed the talk by Gilles a lot. It was a pity that it was not as well attended as it should have been.

At the start of day 4, Dan Spielman gave an excellent talk on using graph theory to solve linear equations. The talk was entitled Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation and the Laplacian was the main character in the story that Dan recounted with verve and clarity. For further reading on this topic, Dan himself suggested this article by Erica Klarreich at the Simon's Foundation. In passing, Dan also described a method for obtaining "obscenely accurate solutions to a problem by solving a simpler one". 


I had had the pleasure to hear Dan deliver a talk on smoothed analysis when he was a co-recipient of the Gödel Prize 2008 in Reykjavík and I watched the video of his talk at the latest ICM. IMHO, the invited talk at ICALP 2012 confirmed him yet again as one of the very best speakers around. 


Day 4 at ICALP 2012 was also devoted to the awards of the Gödel Prize 2012 and of the EATCS Award. As you surely know already, the Gödel Prize went to three seminal papers in the field of Algorithmic Game Theory. Christos Papadimitriou delivered a talk on behalf of the recipients of the Gödel Prize, who were all . present at the conference apart from Noam Nisam. Christos explained the intellectual roots of the concept now known as the price of anarchy and of algorithmic mechanism design. Moreover, he asked the question: What makes an idea spread? His answer was that an idea spreads if it gives young researchers an opportunity to show how smart they are! 


Christos concluded his talk by being a prophet of doom. (I am using his own words here.) He reminded the people in the audience that, for people like me, the "Hello World" program was Max, a program for finding the largest entry in an array of integers, say. The world has changed. Computation has changed. The inputs to our programs are selfish agents who are interested in the outcome of our computation. Vickrey is the new Max :-)

The EATCS Award went to Moshe Vardi (laudatio), who delivered a presentation entitled  A Logical Revolution. In the talk, Moshe described how logic has one from irrelevance to relevance in our field. The key lessons in this rise of logic are the importance of algorithms, heuristics and tools. One of the key insights is that one should not be scared of worst-case complexity: It always barks, but it does not always bite! Efficient in the field of logic in computer science means exponential. "Exponential is the new polynomial." 

Both award presentations were excellent and were given a long round of applause from a packed audience. 


The last invited talk at ICALP 2012 was delivered by Kohei Honda. Kohei´s talk was entitled Session types and distributed computing. It described the origins of the notion of session type and how sessions types find application in the NSF Ocean Observation Initiative. This represents one of the most impressive applications of notions from concurrency theory outside computer science. Kohei is also one of the prime movers behind the programming language Scribble. His talk was a fitting finale to an excellent ICALP conference.

Thanks again to Artur Czumaj and his team for arranging an excellent conference in the beautiful setting of the University of Warwick.