While EC is taking place in Palo-Alto, I just returned from ICALP in Rhodes. ICALP is the main Theoretical CS European conference and is a friendly, relaxed, and fun event with somewhat over 200 participants. Many came with families and many spent some of their time on the beach or in other tourist attractions rather than in the talks. The program consists of 3 tracks: the largest on “Algorithms, automata, complexity and games”, the “European CS” track on “Logic, semantics and theory of programming”, and the new track on “Foundations of networked computation”, with the 3 tracks fitting into two parallel sessions.

The main special event during this ICALP was a workshop celebrating Christos Papadimitriou’s 60th birthday. Dick Karp talked about several algorithmic problems arising from computational biology. Laci Lovasz talked about an elegant notion of a limit of a sequence of graphs. The idea is that we can say that a sequence of graphs , where is a graph on vertices, is convergent if for every finite -vertex graph, the fraction of induced -vertex subgraphs of that equals it, has a limit. For such convergent sequences, an infinite limit object can naturally be defined, where this object turnsa out to be a measurable function , and it maintains various properties of the graphs in the sequence. The next two talks were related to Christos’s current field, Algorithmic Game Theory. I talked about budgets in multi-unit auctions (paper, presentation), and Tim Roughgarden gave an amazingly crisp talk about the robustness of the price of anarchy in congestion games. He pointed out a canonical method used for proving most price-of-anarchy results, and showed that it also bounded the loss incurred in a much wider variety of equilibrium-like solutions, not just pure-Nash equilibria. He also showed that this canonical method is “complete” for congestion games. The last talk of the workshop was given by Christos’s long-time collaborator, Mihalis Yannakakis, who gave an interesting narrative that went over many of the complexity classes that Christos defined throughout his career (such as approximation classes and PPAD). Ending with a few words from Christos, the whole event was really warm and lovely.

Among the regular talks I attended, the one that caught my imagination was by John Reif who has been working on “self-assembly” for the last 10 years and is rarely seen in CS conferences anymore. The idea is to study and mimic natural processes where simple building blocks arrange themselves into complex structures (e.g. into DNA). Theoretical models for this usually involve 2-dimensional tiles that can fit together according to some rules, and this talk gave a probabilistic variant where 1-dimensional tiles also exhibit some capabilities of this form.

Besides the talk I gave during the workshop, I gave another invited talk describing Google’s auction for TV-ads (presentation, paper).

on July 11, 2009 at 5:44 pm |Larry HoskenWow, your editor did interesting things with the formatting of this item as it shows up in my feed reader. A lot of the text got slammed over to the left, all overlapping itself: http://lahosken.san-francisco.ca.us/importable/dense_prose.png

Looking in the source code for the feed, it looks like the editor tried to make several of the text sections be 1pixel x 1 pixel. I see a lot of style=”position:absolute;left:-10000px;top:0;width:1px;height:1px;”

on July 11, 2009 at 10:18 pm |algorithmicgametheoryouch. at least if you go to the web page it looks fine (at least to me).

on July 11, 2009 at 10:07 pm |Jose M VidalIndeed, I am also seeing the same think as Larry.

Great post!

on July 14, 2009 at 12:58 am |Aaron Sterlingis rarely seen in CS conferences anymoreWhile Dave Doty’s FOCS 2009 paper is, I believe, the first self-assembly result to appear in FOCS, STOC or SODA since 2004, there have been self-assembly theory papers appearing steadily in other venues.

John Reif and others founded the Foundations of Nanotechnology (FNANO) conference in 2003, and its main focus is nanostructure self-assembly, though most of the contributions there are biological and experimental, not directly TCS-related. Also focusing on the nano scale, the DNA Computing and Molecular Programming Conference program this year included several self-assembly theory papers.

Some of the most interesting self-assembly work recently has been at the macro scale, for example the papers of Eric Klavins in the robotics and control systems literature. Also, ICALP has steadily included self-assembly results in their program. Doty’s FOCS 09 paper, for example, answers a question raised by Kao and Schweller in an ICALP 2008 paper.

I’ll also mention that the distributed computing community included my own theory of self-assembly work in DISC 2008 and PODC 2009.

For what it’s worth, my take is that there are several researchers publishing interesting ideas along distinct literature tracks, but a comprehensive “theory of self-assembly” has yet to be devised.