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.