ICALP

Ryan O'Donnell, reporting from last week's ICALP in Rhodes.

ICALP has a pretty large number of papers, divided into three tracks. Track A is roughly algorithms and complexity ("Amero-theory"?). Track B is roughly Logic, Semantics, and PL Theory ("Euro-theory"?). Track C, formerly cryptography, is now Foundations of Networked Computation; this seems to appeal most to the Track A people, and sometimes there were mixed A/C tracks.

Three highlights for me were:

• Amin Coja-Oghlan's outstanding paper A better algorithm for random k-SAT, which quite deservedly won Best Paper in Track A. I was very sorry to miss the talk, the earliest in the schedule, as my hydrofoil from Bodrum did not get in till just after it finished. In this paper, Amin gives an O(n^3/2)-time algorithm for random k-SAT which finds satisfying assignments for clause densities up to (ln k / k) 2^k. Much work has gone into this problem, and the previous best algorithm only worked up to density (1.8 / k) 2^k. Although the threshold for satisfiability is (ln 2) 2^k, Amin's work may in fact be "tight": his FOCS 2008 result with Achlioptas gives significant theoretical evidence that (ln k / k) 2^k may be the "algorithmic barrier".
• The special session devoted to Papadimitriou. This proved to be a birthday Festschrift, although it was not advertised as such. Laci Lovasz gave it away (repeatedly) in his invited talk, and the rumour floating around afterwards was that Papadimitriou is indeed "nearly 60" (cf. this). The invited talks here were excellent: Karp, on algorithmic problems from biology; Lovasz, on graph limits; Nisan, on auctions; Roughgarden, on improved methods for analyzing the price of anarchy; and Yannakakis, on complexity-theoretic aspects of Papadimitriou's research. Normally these events are good for getting amusing anecdotes about the fest-ed person, but most stories were quite heartfelt ones about the influence of Papadimitriou on the speaker's work. Possibly the most interesting thing was learning that one of Papadimitriou's most notable contributions to TCS was convincing fellow PhD-student Yannakakis to switch from EE-style information theory to TCS.
• Philip Bille and Mikkel Thorup's paper in which they made the first running-time improvement in 17 years on the problem of regular expression matching; they got it down from nm/log(n) to nm/log^3/2(n) (modulo log log factors). Naturally, Philip name-checked SLOGN in his very nice talk.

We also saw the Greek and Turkish national youth basketball teams at the conference lunches; I believe they skipped all the talks, though.

More from Noam Nisan.

Pictures: view of hotel grounds; view of hotel beach; view of basketball players at the conference lunch.